Sankar Basu
Journal of the Franklin Institute
This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit balls, and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven not to have a polynomial approximation scheme unless P = NP. Specific lower bounds on the error ratios attainable in polynomial time are given, assuming P ≠ NP. In particular, it is shown that covering by two cubes is in P while covering by three cubes is NP-complete. © 1990, Academic Press Limited. All rights reserved.
Sankar Basu
Journal of the Franklin Institute
Igor Devetak, Andreas Winter
ISIT 2003
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Y.Y. Li, K.S. Leung, et al.
J Combin Optim