In a STACS 2003 paper, Talwar analyses the overpayment the
VCG mechanism incurs for ensuring truthfulness in auction. Among other results,
he studies k-Set Cover (given a universe U
and a collection of sets S1, S2,
..., Sq, each having a cost
c(S_i) and at most k
elements of U, find a minimum cost subcollection, called cover, whose
union equals U) and shows that the payment of the optimum cover OPT is at
most k c(OPT'), where OPT' is the best cover disjoint from the
optimum cover.
For k >= 3, k-Set Cover is known to be
NP-Hard, and thus truthful mechanisms based on approximation algorithms are
desirable. We show that the payment incurred by two approximation algorithms
(including the Greedy algorithm) is bounded by (k-1)
c(OPT) + k c(OPT'). The same approximation algorithms have payment
bounded by k (c(OPT) + c(OPT') ) when applied to more
general set systems, which include k -Polymatroid Cover, a problem with
applications in Steiner Tree computations. If q is such that an element
in a k-Set-Cover instance appears in at most q sets, we show that the
payment of our algorithms is bounded by q k2 times the
payment of the optimum algorithm.
No previous knowledge of mechanism design is assumed