Approximation schemes for covering and packing problems in image processing and VLSI.

*(English)*Zbl 0633.68027A 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.

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.

##### MSC:

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 |