On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
type: Item
instance of: scholarly article
title: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
zbMATH Open document ID: 1136.90031
author: Yanyan Li
published in: Mathematical Programming. Series A. Series B
publication date: 2004-10-28T00:00:00Z
review text: The paper interrelates the approximabilities of the metric STSP (Symmetric Traveling Salesman Problem) and the metric ATSP (Asymmetric Traveling Salesman Problem) via the Held-Karp linear programming relaxation of the metric STSP, for which an integrality gap of \(4/3\) was conjectured. Using a new characterization of the integrality gap for general linear objective functions over polyhedra together with the definition of ultra-fundamental, hard-to-round STSP extreme points, it is shown that a slight strengthening of the Held-Karp conjecture would imply also a tight \(4/3\) integrality gap for the metric ATSP.
reviewed by: Kathrin Klamroth
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 2111486
zbMATH Keywords: ATSP
zbMATH Keywords: STSP
zbMATH Keywords: Held-Karp relaxation
zbMATH Keywords: integrality gap
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: s10107-004-0506-y
OpenAlex ID: W2038458261
DOI: 10.1007/S10107-004-0506-Y
description: scientific article; zbMATH DE number 2111486