New bicriteria approximations for bounded-degree TSP variants achieve additive degree violations (+2 for circuits) and match Christofides-Serdyukov cost ratios, answering an open question on additive violations.
Riesenfeld, and Kunal Talwar
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Improved Algorithms for Bounded-Degree (Subset) Traveling Salesman Problems
New bicriteria approximations for bounded-degree TSP variants achieve additive degree violations (+2 for circuits) and match Christofides-Serdyukov cost ratios, answering an open question on additive violations.