We present a variant of the classical set cover problem where the cost
of the cover is more akin to the cost of a join computation over
relations in a database system. We show that several simple heuristics
for this problem can be analyzed in a common linear programming
framework, which bounds both the approximation ratio as well as the
running time. The same formulations also give near tight lower bounds on
the approximation ratio.
(joint work with Shivnath Babu, Rajeev Motwani and Jennifer Widom)