On minimum \(k\)-modal partitions of permutations

DOI10.1016/J.JDA.2008.01.002zbMath1173.90482OpenAlexW2115664516MaRDI QIDQ1018088

Marco E. Lübbecke, Gabriele Di Stefano, Uwe T. Zimmermann, Stefan Krause

Publication date: 13 May 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.01.002

zbMATH Keywords

approximation algorithmcoloringonline algorithmmonotone sequenceLP roundingmixed integer program\(\mathcal{NP}\)-hardnesscocoloring\(k\)-modal sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mixed integer programming (90C11) Permutations, words, matrices (05A05) Combinatorial optimization (90C27)

Related Items (3)

The parallel stack loading problem to minimize blockages ⋮ On the online track assignment problem ⋮ Untangled monotonic chains and adaptive range search

Cites Work

• A tutorial on the use of graph coloring for some problems in robotics
• Online algorithms. The state of the art
• Partitioning a sequence into few monotone subsequences
• Long unimodal subsequences: a problem of F. R. K. Chung
• On unimodal subsequences
• Scheduling trams in the morning
• A survey of stack-sorting disciplines
• Real-time dispatch of trams in storage yards
• Approximating minimum cocolorings.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On Minimum k-Modal Partitions of Permutations
• Selected Topics in Column Generation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On minimum \(k\)-modal partitions of permutations