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 ...
2
votes
Which Integer Linear Programs are easy?
An integer program with only equalities can be solved by linear program.
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
integrality-gap × 13linear-programming × 10
ds.algorithms × 7
approximation-algorithms × 7
reference-request × 3
optimization × 3
integer-programming × 3
cc.complexity-theory × 2
tsp × 2
co.combinatorics × 1
polynomial-time × 1
convex-optimization × 1
semidefinite-programming × 1
combinatorics × 1
max-cut × 1