6 votes
Accepted

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 ...
user avatar
2 votes

Which Integer Linear Programs are easy?

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

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