Campus Event Calendar
Event Entry
What and Who
On Approximating Multi-Criteria TSP
Bodo Manthey
Fachrichtung Informatik - Saarbrücken
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 22 January 2009
10:15
60 Minutes
E1 3 - CS
014
Saarbrücken
Abstract
In many optimization problems, there is more than one objective to be optimized. In this case, there is no natural notion of a best choice. Instead, the goal is to compute a so-called Pareto curve of solutions, which is the set of all solutions that can be considered optimal. Since computing Pareto curves is very often intractable, one has to be content with approximations to them.
We present approximation algorithms for several variants of the multi-criteria traveling salesman problem (TSP), whose approximation performances are independent of the number k of criteria and come close to the approximation ratios obtained for TSP with a single objective function.
First, we present a randomized approximation ratio for multi-criteria Min-ATSP with an approximation ratio of log n + eps, where eps can be made arbitrarily small. Second, we present a randomized 1/2 - eps approximation algorithm for multi-criteria Max-ATSP. This algorithms can be turned into a 2/3 - eps approximation for multi-criteria Max-STSP. Finally, we devise a deterministic 1/4 approximation algorithm for bi-criteria Max-STSP.
Contact
Bodo Manthey
5502
--email hidden
passcode not visible
logged in users only
gk-sek, 01/18/2009 22:00 -- Created document.