File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximating TSP on metrics with bounded global growth

TitleApproximating TSP on metrics with bounded global growth
Authors
Issue Date2008
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2008, p. 690-699 How to Cite?
AbstractThe Traveling Salesman Problem (TSP) is a canonical NP-complete problem which is known to be MAX-SNP hard even on (high-dimensional) Euclidean metrics[39]. In order to circumvent this hardness, researchers have been developing approximation schemes for low-dimensional metrics[4, 38] (under different notions of dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be wellbehaved. In this paper, we consider the ease when the metric is less restricted: it has a few "dense" regions, but is "well-behaved on the average"? To this end, we define a global notion of dimension which we call the correlation dimension (denoted by dim C), which generalizes the popular notion of doubling dimension. In fact, the class of metrics with dimC = O(1) not only contains all doubling metrics, but also contains some metrics containing uniform submetrics of size √n. We first show, using a somewhat "local" argument, that one can solve TSP on these metrics in time 2O(√n) we then take advantage of the global nature of TSP (and the global nature of our definition) to give a (1 +ε) - approximation algorithm that runs in sub-exponential time: i.e., in 2O(nδε -4dimC)-time for every constant 0 < δ < 1.
Persistent Identifierhttp://hdl.handle.net/10722/151938
References

 

DC FieldValueLanguage
dc.contributor.authorHubert Chan, THen_US
dc.contributor.authorGupta, Aen_US
dc.date.accessioned2012-06-26T06:31:14Z-
dc.date.available2012-06-26T06:31:14Z-
dc.date.issued2008en_US
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2008, p. 690-699en_US
dc.identifier.urihttp://hdl.handle.net/10722/151938-
dc.description.abstractThe Traveling Salesman Problem (TSP) is a canonical NP-complete problem which is known to be MAX-SNP hard even on (high-dimensional) Euclidean metrics[39]. In order to circumvent this hardness, researchers have been developing approximation schemes for low-dimensional metrics[4, 38] (under different notions of dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be wellbehaved. In this paper, we consider the ease when the metric is less restricted: it has a few "dense" regions, but is "well-behaved on the average"? To this end, we define a global notion of dimension which we call the correlation dimension (denoted by dim C), which generalizes the popular notion of doubling dimension. In fact, the class of metrics with dimC = O(1) not only contains all doubling metrics, but also contains some metrics containing uniform submetrics of size √n. We first show, using a somewhat "local" argument, that one can solve TSP on these metrics in time 2O(√n) we then take advantage of the global nature of TSP (and the global nature of our definition) to give a (1 +ε) - approximation algorithm that runs in sub-exponential time: i.e., in 2O(nδε -4dimC)-time for every constant 0 < δ < 1.en_US
dc.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleApproximating TSP on metrics with bounded global growthen_US
dc.typeConference_Paperen_US
dc.identifier.emailHubert Chan, TH:hubert@cs.hku.hken_US
dc.identifier.authorityHubert Chan, TH=rp01312en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-58449086439en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-58449086439&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage690en_US
dc.identifier.epage699en_US
dc.identifier.scopusauthoridHubert Chan, TH=12645073600en_US
dc.identifier.scopusauthoridGupta, A=35738763000en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats