Campus Event Calendar
Event Entry
What and Who
Multi-Criteria TSP: Min and Max Combined
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, 2 July 2009
10:15
60 Minutes
E1 3 - CS
415 (4th floor)
Saarbrücken
Abstract
We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized.
For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3-eps, 4+eps) approximate Pareto curves. (The first parameter is the approximation ratio for the max, and the second parameter is the ratio for the min objectives.) For the asymmetric multi-criteria TSP (ATSP), we present an algorithm that computes (1/2-eps, log n + eps) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria TSP with only max objectives.
Contact
gk-sek
5502
--email hidden
passcode not visible
logged in users only
gk-sek, 06/19/2009 11:06
gk-sek, 06/19/2009 11:04 -- Created document.
gk-sek, 06/19/2009 11:04 -- Created document.