TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2005

COGA 5-Wheel


zur Navigation

Preprints 2005

On Minimum Monotone and Unimodal Partitions of Permutations
Zitatschlüssel Report-007-2005
Autor Gabriele Di Stefano and Stefan Krause and Marco E. Lübbecke and Uwe T. Zimmermann
Jahr 2005
Nummer 007
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Partitioning a permutation into a minimum number of monotone subsequences is NP-hard. We extend this complexity result to minimum partitions into unimodal subsequences. In graph theoretical terms these problems are cocoloring and what we call split-coloring of permutation graphs. Based on a network flow interpretation of both problems we introduce mixed integer programs; this is the first approach to obtain optimal partitions for these problems in general. We derive an LP rounding algorithm which is a 2-approximation for both coloring problems. It performs much better in practice. In an online situation the permutation becomes known to an algorithm sequentially, and we give a logarithmic lower bound on the competitive ratio and analyze two online algorithms.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe