𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of some geometric problems in unbounded dimension

✍ Scribed by Nimrod Megiddo

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
429 KB
Volume
10
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

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 ball% 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.

πŸ“œ SIMILAR VOLUMES

On the Complexity of Some Problems on Gr
On the Complexity of Some Problems on Groups Input as Multiplication Tables
✍ David Mix Barrington; Peter Kadau; Klaus-JΓΆrn Lange; Pierre McKenzie πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 131 KB

The Cayley group membership problem (CGM) is to input a groupoid (binary algebra) G given as a multiplication table, a subset X of G, and an element t of G and to determine whether t can be expressed as a product of elements of X. For general groupoids CGM is P-complete, and for associative algebras

On the existence of positive solutions f
On the existence of positive solutions for some nonlinear elliptic problems in unbounded domain in
✍ Syrine Masmoudi πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 238 KB

We are interested in the following nonlinear elliptic equation u + u (., u) = 0 in D, where D is a smooth unbounded domain in R 2 . Under appropriate conditions on the nonlinearity (x, t), related to a certain Kato class, we give some existence results and asymptotic behavior for positive solutions

On the complexity of the continuous unbo
On the complexity of the continuous unbounded knapsack problem with uncertain coefficients
✍ Eduardo Conde πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 166 KB

In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of O(n lo