A $(\frac32+\frac1\mathrme)$-Approximation Algorithm for Ordered TSP
<|reference_start|>A $(\frac32+\frac1\mathrme)$-Approximation Algorithm for Ordered TSP: We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.<|reference_end|>
@article{armbruster2024a,
    title={A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP},
    author={Susanne Armbruster, Matthias Mnich, Martin N"agele},
    journal={arXiv preprint arXiv:2405.06244},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.06244},
    primaryClass={cs.DS}
}