Classification and approximation of geometric location problems / Sascha Brauer, M. Sc. ; [Prof. Dr. Johannes Blömer, Paderborn University, Prof. Dr. Heiko Röglin, University of Bonn]. Paderborn, 2019
Inhalt
- Introduction
- Fundamentals
- Classification and Impossibility
- Classical Hardness
- Basics of Computational Complexity
- Discrete Clustering Problems
- Related Work
- Towards a Classification of DFKM
- Parameterized Hardness of DFRKM
- DKM is Hard in Fixed Dimensions
- Complexity of Single-Swap Local Search
- Polynomial Local Search
- Related Work
- Completeness of MUFL/SingleSwap
- Completeness of DKM/SingleSwap
- Completeness of DFKM/SingleSwap
- Non-Representability of Solutions
- Approaching Hard Problems