The computational complexity and approximability of a series of geometric covering problems
DOI10.1134/S008154381309006XzbMath1317.68075OpenAlexW2105177507MaRDI QIDQ483201
M. I. Poberii, Mikhail Yu. Khachay
Publication date: 16 December 2014
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s008154381309006x
NP-complete problempolynomial-time approximation scheme (PTAS)\(L\)-reductionMAX-SNP-hard problempolynomial-time reduction
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Exact and approximation algorithms for clustering
- On the complexity of locating linear facilities in the plane
- Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
- Covering things with things
- Fast multiplication of large numbers
- A threshold of ln n for approximating set cover
This page was built for publication: The computational complexity and approximability of a series of geometric covering problems
