Discrete Time-Cost Tradeoff Problem

From himtp
Revision as of 08:58, 22 September 2015 by Vygen (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(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