@techreport{Report-007-2005,
Title = {On Minimum Monotone and Unimodal Partitions of Permutations},
Author = {Gabriele Di Stefano and Stefan Krause and Marco E. L\"ubbecke and Uwe T. Zimmermann},
Year = {2005},
Number = {007},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
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.},
Url = {http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2005/Report-007-2005.pdf},
Keywords = {Permutation; monotone sequence; unimodal sequence; NP-hardness; cocoloring; mixed integer program; LP rounding; approximation algorithm; online algorithm}
}