2 votes

Which Integer Linear Programs are easy?

An integer program with only equalities can be solved by linear program.
Turbo's user avatar
  • 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 ...
NaturalLogZ's user avatar

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