Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4, D5
What and Who
(Non-)Approximability of Restricted Cycle Covers
Bodo Manthey
Universität zu Lübeck
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 2 November 2005
13:30
-- Not specified --
46.1 - MPII
024
Saarbrücken
Abstract
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. Cycle covers play an important role in the design of approximation algorithms for combinatorial optimisation problems such as the travelling salesman problem. To improve the approximation ratios achieved by cycle cover based algorithms, it is helpful to rule out certain cycle lengths a priori. Therefore, we consider restricted cycle covers: An L-cycle cover is a cycle cover in which the cycle lengths are restricted to be in the set L.
We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is hard to approximate, and deciding whether a graph contains an L-cycle cover is NP-hard. Most of our hardness results hold even if the edge weights are restricted to be zero or one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated with a factor of 2.5 for undirected graphs and with a factor of 3 in the case of directed graphs. These approximation algorithms work for arbitrary sets L.
Contact
Benjamin Doerr
104
--email hidden
passcode not visible
logged in users only
Christian Klein, 11/09/2005 23:11
Christian Klein, 10/21/2005 15:16 -- Created document.
Christian Klein, 10/21/2005 15:16 -- Created document.