# Discrete Time-Cost Tradeoff Problem

(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 . Knapsack cover inequalities do not help.

# Challenge

Find an -approximation algorithm. Find an LP (or SDP) formulation with an integrality ratio.