2
votes
Which Integer Linear Programs are easy?
An integer program with only equalities can be solved by linear program.
- 12.8k
1
vote
What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?
Are you asking about lower or upper bounds on the integrality gap? For lower bounds, we know that the gap is at least 4/3. That example that shows this is planar, graphic, and Euclidean (well each of ...
- 226
Only top scored, non community-wiki answers of a minimum length are eligible