The asymmetric traveling salesman path LP has constant integrality ratio
成果类型：
Article
署名作者：
Koehne, Anna; Traub, Vera; Vygen, Jens
署名单位：
University of Bonn; University of Bonn
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01450-8
发表日期：
2020
页码：
379-395
关键词：
摘要：
We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If.ATSP and.ATSPP denote the integrality ratios for the asymmetric TSP and its path version, then.ATSPP = 4.ATSP - 3. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is.NWATSP, then the integrality ratio for ATSPP on node-weighted instances is at most 2.NW ATSP - 1. Moreover, we show that for ATSP node-weighted instances and unweighted digraph instances are almost equivalent. From this we deduce a lower bound of 2 on the integrality ratio of unweighted digraph instances.