License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.284
URN: urn:nbn:de:0030-drops-47034
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4703/
Go to the corresponding LIPIcs Volume Portal

Karp, Jeremy A. ; Ravi, R.

A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs

pdf-format:
20.pdf (0.5 MB)

Abstract

We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time 9/7-approximation algorithm for cubic bipartite graphs and a (9/7+1/(21(k-2)))-approximation algorithm for k-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.

BibTeX - Entry

@InProceedings{karp_et_al:LIPIcs:2014:4703,
  author =	{Jeremy A. Karp and R. Ravi},
  title =	{{A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{284--296},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4703},
  URN =		{urn:nbn:de:0030-drops-47034},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.284},
  annote =	{Keywords: Approximation algorithms, traveling salesman problem, Barnette’s conjecture, combinatorial optimization}
}

Keywords: Approximation algorithms, traveling salesman problem, Barnette’s conjecture, combinatorial optimization
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI