The Asymmetric Traveling Salesman Path LP Has Constant Integrality Ratio.
Anna KöhneVera TraubJens VygenPublished in: IPCO (2019)
Keyphrases
- traveling salesman
- mixed integer
- extreme points
- linear programming
- lp relaxation
- linear program
- traveling salesman problem
- quadratic assignment problem
- global optimization
- shortest path
- objective function
- linear programming relaxation
- linear systems
- knapsack problem
- integer programming
- valid inequalities
- primal dual
- lot sizing
- message passing
- feasible solution
- dynamic programming
- optimal solution