The computational complexity and approximability of a series of geometric covering problems
type: Item
instance of: scholarly article
title: The computational complexity and approximability of a series of geometric covering problems
zbMATH Open document ID: 1317.68075
DOI: 10.1134/S008154381309006X
author: M. I. Poberii
author: M. Yu. Khachaĭ
published in: Proceedings of the Steklov Institute of Mathematics
publication date: 2014-12-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 6380784
zbMATH Keywords: NP-complete problem
zbMATH Keywords: polynomial-time reduction
zbMATH Keywords: MAX-SNP-hard problem
zbMATH Keywords: \(L\)-reduction
zbMATH Keywords: polynomial-time approximation scheme (PTAS)
MaRDI profile type: Publication
cites work: Exact and approximation algorithms for clustering
cites work: Covering things with things
cites work: Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: A threshold of ln n for approximating set cover
cites work: On the complexity of locating linear facilities in the plane
cites work: Optimization, approximation, and complexity classes
cites work: Fast multiplication of large numbers
full work available at URL: s008154381309006x
OpenAlex ID: W2105177507
description: scientific article; zbMATH DE number 6380784