Abstract

We provide preliminary results regarding the existence of a polynomial time approximation scheme (PTAS) for minimizing a linear function over a 0/1 covering polytope which is integral, with one additional covering constraint. Our algorithm is based on extending the methods of Goemans and Ravi for the constrained minimum spanning tree problem and, in particular, implies the existence of a PTAS for several covering integer programming problems with a totally unimodular constraint matrix. These include the cases when the columns of the constraint matrix either: have at most two nonzero elements; are incidence vectors of a laminar family; or have consecutive ones and no column is contained in another. © 2009 INFORMS.