Integrality Gap and Rounding

When you are coming up with an approximation algorithm for some NP-hard maximization problem, there are several values that you might care about: There is \(OPT\), the optimal value of your problem, which is the same as \(OPT(IP)\), the optimal value of any correct IP formulation of your problem. There is also \(OPT(LP)\), the optimal value of the linear relaxation of your IP. We have \(OPT(LP)≥OPT(IP)\). Finally, there is V, the value of the solution you end up getting by rounding the LP solution. You would like to be able to prove that \(V>OPT(IP)\cdot c\) to show that your algorithm is a \(c\)-approximation, but it is often not possible to do this directly, since you don't have a hold on the solution space. Instead, what is almost always proven is that \(V≥OPT(LP)\cdot c\) . This of course implies \(V>OPT(IP)\cdot c\) , but is stronger. In particular, if the integrality gap of your IP formulation is larger than \(c\) , the above statement will be false in general, since your rounding procedure ends up with an integral solution. So the crux is this: The LP gives you a solution which you know is "good", and you want to round it to something that is "almost as good". If the integrality gap is large, this is impossible in general, since there will never be a procedure which is guaranteed to get an integral solution that is "amost as good" as an LP solution -- because sometimes, these don't exist!

Hardness of Shortest Path

  • Allowing only non-negative weight edges, Shortest-Path=Shortest Simple Path, polynomial-time solvable
  • Allowing negative weight, but no negative cycle, Shortest-Path = Shortest Simple Path, Dijkstra won't work, but Bellman-Ford works in polynomial time
  • Allowing negative weight, allowing negative cycle, Shortest Path makes no sense, Shortest Simple Path is NP-hard by reducing from Longest Simple Path problem (negating the weight of all edges)
  • Longest Simple Path is NP-hard by reduction from Hamiltonian Path: Take any graph, assign each edge weight of \(1\), then the graph is Hamiltonian \(if.f.\) longest simple path has length \(n-1\)

    • In any sense, Shortest Path problem is indeed Shortest Simple Path problem