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

From himtp
Jump to: navigation, search
(Problem Statement)
Line 4: Line 4:
  
 
Let <math> \sqrt{f(G)} </math> be an acyclic digraph.
 
Let <math> \sqrt{f(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).
Moreover, there is a deadline <math>D>0<\math>.
+
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>
+
Let <math>\mathcal{P}</math> be the set of all maximal paths in <math>G</math>
  
The task is to find an edge set <math> F\subseteq E(G) <\math> (the fast edges) such that
+
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>
+
<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>.  
+
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>.
 
Among all such solutions we would like to minimize <math>c(F):=\sum_{e\in F} c(e)</math>.
  
 
= 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.

Revision as of 07:53, 22 September 2015

(suggested by Jens Vygen)

Problem Statement

Let  \sqrt{f(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 Failed to parse (unknown function "\math"): -approximation algorithm. Find an LP (or SDP) formulation with an o(n) integrality ratio.

State of the Art