The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio.

András Sebö Anke van Zuylen

Published in: CoRR (2016)

Keyphrases

approximation ratio
approximation algorithms
integrality gap
approximation guarantees
np hard
special case
greedy algorithm
search algorithm
minimum cost
shortest path
linear programming relaxation
np hardness
linear programming
linear program
primal dual
valid inequalities