# Difference between revisions of "Discrete Time-Cost Tradeoff Problem"

(6 intermediate revisions by the same user not shown) | |||

Line 3: | Line 3: | ||

= Problem Statement = | = Problem Statement = | ||

− | Let <math> | + | Let <math>G</math> be an acyclic digraph. |

For each edge <math>e</math> we have execution times <math> 0 \le \tau_1(e) \le \tau_2(e) </math> | For each edge <math>e</math> we have execution times <math> 0 \le \tau_1(e) \le \tau_2(e) </math> | ||

and an acceleration cost <math> c(e) </math> (that we pay if we make the edge fast). | and an acceleration cost <math> c(e) </math> (that we pay if we make the edge fast). | ||

Line 16: | Line 16: | ||

= What is known? = | = What is known? = | ||

− | The best known approximation algorithm has approximation ratio <math>\max_{P\in\mathcal{P}}|E(P)|</math>. | + | The best known approximation algorithm has approximation ratio <math> \max_{P\in\mathcal{P}} |E(P)| </math>. |

The problem cannot be approximated better than VERTEX COVER, and there is no constant-factor | The problem cannot be approximated better than VERTEX COVER, and there is no constant-factor | ||

approximation algorithm if the Unique Games Conjecture holds. | approximation algorithm if the Unique Games Conjecture holds. | ||

− | The standard LP (via set covering) has integrality ratio <math>\Omega(n)< | + | The standard LP (via set covering) has integrality ratio <math>\Omega(n)</math>. |

Knapsack cover inequalities do not help. | Knapsack cover inequalities do not help. | ||

= Challenge = | = Challenge = | ||

− | Find | + | Find an <math>o(n)</math>-approximation algorithm. |

Find an LP (or SDP) formulation with an <math>o(n)</math> integrality ratio. | Find an LP (or SDP) formulation with an <math>o(n)</math> integrality ratio. | ||

− | = | + | = Please add comments here = |

## Latest revision as of 08:58, 22 September 2015

(suggested by Jens Vygen)

# Problem Statement

Let be an acyclic digraph. For each edge we have execution times and an acceleration cost (that we pay if we make the edge fast). Moreover, there is a deadline . Let be the set of all maximal paths in

The task is to find an edge set (the fast edges) such that for all . Among all such solutions we would like to minimize .

# What is known?

The best known approximation algorithm has approximation ratio . The problem cannot be approximated better than VERTEX COVER, and there is no constant-factor approximation algorithm if the Unique Games Conjecture holds.

The standard LP (via set covering) has integrality ratio . Knapsack cover inequalities do not help.

# Challenge

Find an -approximation algorithm. Find an LP (or SDP) formulation with an integrality ratio.