2026-07-22T21:28:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24387 2025-12-12T15:01:21Z ddc:004 open_access

Dual Charging for Half-Integral TSP Klein, Nathan Taziki, Mehrshad Approximation Algorithms Graph Algorithms Randomized Rounding Linear Programming In this extended abstract, we show that the max entropy algorithm is a randomized 1.49776 approximation for half-integral TSP, improving upon the previous known bound of 1.49993 from Karlin et al. This also improves upon the best-known approximation for half-integral TSP due to Gupta et al. Our improvement results from using the dual, instead of the primal, to analyze the expected cost of the matching. We believe this method of analysis could lead to a simpler proof that max entropy is a better-than-3/2 approximation in the general case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathan Klein and Mehrshad Taziki 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.21 urn:nbn:de:0030-drops-243879 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode