P. M. Long. Using the pseudo-dimension to analyze
approximation algorithms for integer programming.
Proceedings of the Seventh
International Workshop on Algorithms and Data Structures, 2001.
(Available in Postscript and PDF formats.)
Abstract
We prove approximation guarantees for randomized algorithms
for packing and covering integer programs expressed in certain
normal forms. The bounds are in terms of the pseudo-dimension of the
matrix of the coefficients of the constraints and the value of the optimal
solution; they are independent of the number of constraints and the
number of variables. The algorithms take time polynomial in the length
of the representation of the integer program and the value of the optimal
solution. We establish a related result for a class we call the mixed covering
integer programs, which contains the covering integer programs. We
describe applications of these techniques and results to a generalization
of Dominating Set motivated by distributed file sharing applications, to
an optimization problem motivated by an analysis of boosting, and to a
generalization of matching in hypergraphs.