The computational complexity and approximability of a series of geometric covering problems

DOI10.1134/S008154381309006XMaRDI QIDQ483201zbMATH OpenOpenAlexFDO

Authors M. I. Poberii, M. Yu. Khachaĭ

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

zbMATH Keywords

NP-complete problempolynomial-time approximation scheme (PTAS)\(L\)-reductionMAX-SNP-hard problempolynomial-time reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial problems
• Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
• Covering things with things
• Exact and approximation algorithms for clustering
• Fast multiplication of large numbers
• On the complexity of locating linear facilities in the plane
• On the ratio of optimal integral and fractional covers
• Optimization, approximation, and complexity classes

Cited in

(8)

• The complexity of the covering radius problem
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• Covering a simplex by spheres: complexity and algorithms
• scientific article; zbMATH DE number 5790346 (Why is no real title available?)
• Parameterized complexity of geometric covering problems having conflicts
• On the approximability of covering points by lines and related problems
• Angle covers: algorithms and complexity
• scientific article; zbMATH DE number 2081090 (Why is no real title available?)

This page was built for publication: The computational complexity and approximability of a series of geometric covering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483201)