NDLI: Approximating TSP on Metrics with Bounded Global Growth

Please wait, while we are loading the content...

Approximating TSP on Metrics with Bounded Global Growth

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Gupta, Anupam Hubert Chan, T.-H.
Copyright Year	2012
Abstract	The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475--485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for simpler instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are local: the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size $\sqrt{n}$. Given a metric with global dimension $\dim_{C}$, we give a $(1+\varepsilon)$-approximation algorithm that runs in subexponential time, i.e., in $\exp(O(n^{\delta}\varepsilon^{-4\dim_{C}}))$-time for every constant $0<\delta<1$. As mentioned above, metrics with bounded $\dim_{C}$ may contain metrics of size $O(\sqrt{n})$ on which the TSP problem is hard to approximate to within $(1+\varepsilon)$. Hence, to do better than a running time of $\Omega(\exp\{\sqrt{n}\})$, our algorithms find $O(1)$-approximations to some portions of the tour, and $(1+\varepsilon)$-approximations for other portions, and stitch them together. Moreover, we show that such globally bounded metrics have spanners that preserve distances to arbitrary accuracy and have size $\Theta(n^{1.5})$.
Starting Page	587
Ending Page	617
Page Count	31
File Format	PDF
ISSN	00975397
DOI	10.1137/090749396
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	41
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2012-05-31
Access Restriction	Subscribed
Subject Keyword	metric spanners traveling salesman problem global notion of dimension Approximation algorithms approximation algorithms Metric theory of other algorithms and expansions; measure and Hausdorff dimension
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Abstract approximating tsp on metrics with bounded global growth ∗.

Approximating TSP on Metrics with Bounded Global Growth (2008)

Approximating tsp on metrics with bounded global growth.

Approximating TSP on metrics with bounded global growth (2008)

Approximation algorithms for the traveling salesman problem

Analysis of a near-metric TSP approximation algorithm

The Duffin-Schaeffer Conjecture with extra divergence

The Duffin-Schaeffer Conjecture with extra divergence II

Approximation algorithms for the traveling salesman problem

Approximating TSP on Metrics with Bounded Global Growth

Similar Documents

Abstract approximating tsp on metrics with bounded global growth ∗.

Approximating TSP on Metrics with Bounded Global Growth (2008)

Approximating tsp on metrics with bounded global growth.

Approximating TSP on metrics with bounded global growth (2008)

Approximation algorithms for the traveling salesman problem

Analysis of a near-metric TSP approximation algorithm

The Duffin-Schaeffer Conjecture with extra divergence

The Duffin-Schaeffer Conjecture with extra divergence II

Approximation algorithms for the traveling salesman problem

Approximating TSP on Metrics with Bounded Global Growth