On Minimum k-Modal Partitions of Permutations
DOI10.1007/11682462_36zbMath1145.90435MaRDI QIDQ3525774
Gabriele Di Stefano, Marco E. Lübbecke, Stefan Krause, Uwe T. Zimmermann
Publication date: 18 September 2008
Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11682462_36
approximation algorithm; online algorithm; monotone sequence; LP rounding; mixed integer program; \(\mathcal {NP}\)-hardness; cocoloring; \(k\)-modal sequence
68Q25: Analysis of algorithms and problem complexity
90C11: Mixed integer programming
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)