The asymmetric traveling salesman path LP has constant integrality ratio.
Anna KöhneVera TraubJens VygenPublished in: Math. Program. (2020)
Keyphrases
- traveling salesman
- mixed integer
- linear programming
- traveling salesman problem
- extreme points
- lp relaxation
- linear program
- quadratic assignment problem
- global optimization
- linear systems
- shortest path
- message passing
- objective function
- linear programming relaxation
- combinatorial optimization
- multi class
- scheduling problem