On Minimum Monotone and Unimodal Partitions of Permutations

Simple item page
dc.contributor.authorStefano, Gabriele Di
dc.contributor.authorKrause, Stefan
dc.contributor.authorLübbecke, Marco E.
dc.contributor.authorZimmermann, Uwe T.
dc.date.accessioned2021-12-17T10:06:37Z
dc.date.available2021-12-17T10:06:37Z
dc.date.issued2005
dc.description.abstractPartitioning 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15570
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14343
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherpermutationen
dc.subject.othermonotone sequenceen
dc.subject.otherunimodal sequenceen
dc.subject.otherNP-hardnessen
dc.subject.othercocoloringen
dc.subject.othermixed integer programen
dc.subject.otherLP roundingen
dc.subject.otherapproximation algorithmen
dc.subject.otheronline algorithmen
dc.titleOn Minimum Monotone and Unimodal Partitions of Permutationsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2005, 07en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200090C11 Mixed integer programmingen
tub.subject.msc200005A05 Combinatorial choice problemsen
tub.subject.msc200068Q25 Analysis of algorithms and problem complexityen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Report-007-2005.pdf
Size:
246.65 KB
Format:
Adobe Portable Document Format
Download

Collections

Publications