(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 a poly<\math>\log(n)[/itex]-approximation algorithm. Find an LP (or SDP) formulation with an $o(n)$ integrality ratio.