Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem

Yuval Rabani and Gabriel Scalosub

Abstract:

We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2,O(log n)) bicriteria approximation, i.e. the solution's profit is at least an O(log n) fraction of an optimum solution respecting the budget, while its cost is at most twice the given budget.
We improve these results and present a bicriteria tradeoff that, given any 0 < \eps \leq 1, guarantees a (1+\eps,O(log n)/\eps)-approximation.