From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization

Lukas Behrendt, Katrin Casel, Tobias Friedrich +3

We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the…