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

From himtp
Jump to: navigation, search
(Problem Statement)
 
(17 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
= Problem Statement =
 
= Problem Statement =
  
Let <math> sqrt(f(G)) </math> be a directed acyclic graph....
+
Let <math>G</math> be an acyclic digraph.
to be written
+
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).
 +
Moreover, there is a deadline <math>D\ge 0</math>.
 +
Let <math>\mathcal{P}</math> be the set of all maximal paths in <math>G</math>
  
= State of the Art =
+
The task is to find an edge set <math> F\subseteq E(G) </math> (the fast edges) such that
 +
<math> \sum_{e\in E(P)\cap F} \tau_1(e) + \sum_{e\in E(P)\setminus F} \tau_2(e) \le D</math>
 +
for all <math> P\in\mathcal{P}</math>.
 +
Among all such solutions we would like to minimize <math>c(F):=\sum_{e\in F} c(e)</math>.
 +
 
 +
= What is known? =
 +
 
 +
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
 +
approximation algorithm if the Unique Games Conjecture holds.
 +
 
 +
The standard LP (via set covering) has integrality ratio <math>\Omega(n)</math>.
 +
Knapsack cover inequalities do not help.
 +
 
 +
= Challenge =
 +
 
 +
Find an <math>o(n)</math>-approximation algorithm.
 +
Find an LP (or SDP) formulation with an <math>o(n)</math> integrality ratio.
 +
 
 +
= Please add comments here =

Latest revision as of 07:58, 22 September 2015

(suggested by Jens Vygen)

Problem Statement

Let G be an acyclic digraph. For each edge e we have execution times  0 \le \tau_1(e) \le \tau_2(e) and an acceleration cost  c(e) (that we pay if we make the edge fast). Moreover, there is a deadline D\ge 0. Let \mathcal{P} be the set of all maximal paths in G

The task is to find an edge set  F\subseteq E(G) (the fast edges) such that  \sum_{e\in E(P)\cap F} \tau_1(e) + \sum_{e\in E(P)\setminus F} \tau_2(e) \le D for all  P\in\mathcal{P}. Among all such solutions we would like to minimize c(F):=\sum_{e\in F} c(e).

What is known?

The best known approximation algorithm has approximation ratio  \max_{P\in\mathcal{P}} |E(P)| . 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 \Omega(n). Knapsack cover inequalities do not help.

Challenge

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

Please add comments here