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

(→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< | + | 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 | + | 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< | + | 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) < | + | 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> \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}< | + | 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)|< | + | 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 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 **Failed to parse (unknown function "\math"): **
-approximation algorithm.
Find an LP (or SDP) formulation with an integrality ratio.