An improved upper bound on the integrality ratio for the $s$-$t$-path TSP

August 31, 2018 ยท The Ethereal ยท ๐Ÿ› Operations Research Letters

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Vera Traub, Jens Vygen arXiv ID 1808.10734 Category cs.DM: Discrete Mathematics Cross-listed cs.DS, math.CO Citations 10 Venue Operations Research Letters Last Checked 2 months ago
Abstract
We give an improved analysis of the best-of-many Christofides algorithm with lonely edge deletion, which was proposed by Sebล‘ and van Zuylen [2016]. This implies an improved upper bound on the integrality ratio of the standard LP relaxation for the $s$-$t$-path TSP.
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Discrete Mathematics