zbMATH — the first resource for mathematics

Approximation schemes for covering and packing problems in image processing and VLSI. (English) Zbl 0633.68027
A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error \(\epsilon >0\), with running time that is polynomial when \(\epsilon\) is fixed. Though the polynomiality of these algorithms depends on the degree of approximation \(\epsilon\) being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP- complete problems unless \(NP=P.\)
The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs.

68Q25 Analysis of algorithms and problem complexity
11H31 Lattice packing and covering (number-theoretic aspects)
94C30 Applications of design theory to circuits and networks
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
Full Text: DOI