Approximating Multi-Criteria Max-TSP
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
We present randomized approximation algorithms for multi-criteria Max-TSP. For Max-STSP with k > 1 objective functions, we obtain an approximation ratio of $1/k - \eps$ for arbitrarily small $\eps > 0$. For Max-ATSP with k objective functions, we obtain an approximation ratio of $1/(k+1) - \eps$.
An extended abstract of this worl will appear in Proc. of the 16th Ann. European Symposium on Algorithms (ESA 2008)
An extended abstract of this worl will appear in Proc. of the 16th Ann. European Symposium on Algorithms (ESA 2008)