Bots, Bureaucrats, editor
84
edits
Changes
From Theory
Created page with "== Title == Maximum ATSP with Weights Zero and One via Half-Edges == Speaker == Katarzyna Paluch == Abstract == In the maximum asymmetric traveling salesman problem (Max ATS..."
== Title ==
Maximum ATSP with Weights Zero and One via Half-Edges
== Speaker ==
Katarzyna Paluch
== Abstract ==
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight.
In this paper we give a fast combinatorial 3/4-approximation algorithm for Max ATSP. It is based on a novel technique of eliminating problematic subgraphs with the aid of half-edges
and a new method of edge coloring. (A half-edge of edge (u,v) is informally speaking ``either a head or a tail of (u,v)''.)
The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of 2/3, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a recent result by Mucha (2013), we obtain also a 2 11/30 ~ 2,3667-approximation algorithm for the shortest superstring problem (SSP), beating the previously best known (having approximation factor equal to 2,4782.)
Maximum ATSP with Weights Zero and One via Half-Edges
== Speaker ==
Katarzyna Paluch
== Abstract ==
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight.
In this paper we give a fast combinatorial 3/4-approximation algorithm for Max ATSP. It is based on a novel technique of eliminating problematic subgraphs with the aid of half-edges
and a new method of edge coloring. (A half-edge of edge (u,v) is informally speaking ``either a head or a tail of (u,v)''.)
The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of 2/3, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a recent result by Mucha (2013), we obtain also a 2 11/30 ~ 2,3667-approximation algorithm for the shortest superstring problem (SSP), beating the previously best known (having approximation factor equal to 2,4782.)
