On explaining integer vectors by few homogeneous segments
From MaRDI portal
Publication:2256725
DOI10.1016/j.jcss.2014.12.028zbMath1320.68098MaRDI QIDQ2256725
Jiehua Chen, Sepp Hartung, Ondřej Suchý, Christian Komusiewicz, Robert Bredereck, Rolf Niedermeier
Publication date: 20 February 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2014.12.028
NP-hardness; parameterized complexity; exact algorithms; multivariate algorithmics; matrix and vector decomposition
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Shape rectangularization problems in intensity-modulated radiation therapy
- Parameterizing by the number of numbers
- A shortest path-based approach to the multileaf collimator sequencing problem
- Approximation algorithms for minimizing segments in radiation therapy
- Simple upper bounds for partition functions
- An application of simultaneous diophantine approximation in combinatorial optimization
- Parameterized complexity of vertex colouring
- Faster optimal algorithms for segment minimization with small maximal value
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- A note on improving the performance of approximation algorithms for radiation therapy
- Parametrized complexity theory.
- Decomposition of integer matrices and multileaf collimator sequencing
- New Races in Parameterized Algorithmics
- Integer Programming with a Fixed Number of Variables
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Minkowski's Convex Body Theorem and Integer Programming
- Kernelization Lower Bounds by Cross-Composition
- Parameterized and Exact Computation
- Mathematical optimization in intensity modulated radiation therapy