Metadata only
Date
2014Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We introduce a general model for time-expanded versions of packing problems with a variety of applications. Our notion for time-expanded packings, which we introduce in two natural variations, requires elements to be part of the solution for several consecutive time steps. Despite the fact that the time-expanded counterparts of most combinatorial optimization problems become computationally hard to solve, we present strong approximation algorithms for general dependence systems and matroids, respectively, depending on the considered variant. More precisely, for both notions of time-expanded packings that we introduce, the approximation guarantees we obtain are at most a small constant-factor worse than the best approximation algorithms for the underlying problem in its non-time-expanded version. Show more
Publication status
publishedExternal links
Book title
Automata, Languages, and ProgrammingJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
08694 - Gruppe Zenklusen
03873 - Weismantel, Robert / Weismantel, Robert
More
Show all metadata
ETH Bibliography
yes
Altmetrics