Discrete Time-Cost Tradeoff Problem
(suggested by Jens Vygen)
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 . Knapsack cover inequalities do not help.
Find an -approximation algorithm. Find an LP (or SDP) formulation with an integrality ratio.