direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 07-2005

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
On Minimum Monotone and Unimodal Partitions of Permutations
Authors
Classification
MSC:
primary: 90C27 Combinatorial optimization
secondary: 90C11 Mixed integer programming
05A05 Combinatorial choice problems
68Q25 Analysis of algorithms and problem complexity
Keywords
Permutation; monotone sequence; unimodal sequence; NP-hardness; cocoloring; mixed integer program; LP rounding; approximation algorithm; online algorithm
Abstract
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.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe