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

TLDR

The shifting strategy, also independently developed by Baker for planar graphs, offers polynomial approximation schemes for many strongly NP‑complete geometric covering and packing problems, but cannot be improved to fully polynomial schemes unless NP = P. The paper presents a unified approach for devising polynomial approximation schemes for a wide range of strongly NP‑complete problems. The method employs a shifting strategy that generates families of approximation algorithms with polynomial running time for fixed ε, and illustrates how the technique adapts to different problem parameters. The authors demonstrate that no fully polynomial approximation schemes exist for strongly NP‑complete problems unless NP = P, and that their shifting strategy yields polynomial schemes for numerous geometric covering and packing problems.

Abstract

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 ε > Ο, with running time that is polynomial when ε is fixed. Though the polynomiality of these algorithms depends on the degree of approximation ε 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.