6 votes

Greedy vs LP Approximation

Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of ...
2 votes

Which Integer Linear Programs are easy?

An integer program with only equalities can be solved by linear program.
  • 12.5k

Only top scored, non community-wiki answers of a minimum length are eligible