Approximation Schemes for Covering and Packing in the Streaming Model

Christopher Liaw, Paul Liu, Robert Reiss

The shifting strategy, introduced by Hochbaum and Maass, and independently by Baker, is a unified framework for devising polynomial approximation schemes to NP-Hard problems. This…