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 ...
- 9,566
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