ARC Colloquium: Ola Svensson, École polytechnique fédérale de Lausanne EPFL

Event Details
  • Date/Time:
    • Wednesday October 19, 2011
      1:30 pm
  • Location: Klaus 1116W, Georgia Tech, Atlanta GA
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

Prasad Tetali
Director, Algorithms Research Center

Summaries

Summary Sentence: Approximating Graphic TSP by Matchings

Full Summary:
We present a framework for approximating the metric TSP based on a novel use of matchings.


We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.

For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.

This is joint work with Tobias Momke.

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
approximation algorithm, claw-free graphs, graph-TSP, Held-Karp, traveling salesman path
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Oct 14, 2011 - 7:39am
  • Last Updated: Oct 7, 2016 - 9:56pm