Bodo Manthey — Deterministic Algorithms for Multi-Criteria TSP
| Time: | Wednesday, May 4, 2011 |
| Location: | Room 101, Citadel |
We present deterministic approximation algorithms for the multi-criteria traveling salesman problem (TSP). Our algorithms are faster and simpler than the existing randomized algorithms. In the talk, we will mainly focus on a 1/4 - ε approximation for bi-criteria Max-ATSP.