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

From himtp
Jump to: navigation, search
 
(6 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
= Problem Statement =
 
= Problem Statement =
  
Let <math> \sqrt{f(G)} </math> be an acyclic digraph.
+
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)<\math>.  
+
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 a poly<\math>\log(n)</math>-approximation algorithm.
+
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.
  
= State of the Art =
+
= 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