M.Sc Thesis
M.Sc Student Scalosub Gabriel Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem Department of Computer Science Professor Yuval Rabani

Abstract

Many interesting optimization problems are NP-hard. One way to cope with such problems is to settle for approximate solutions. An extension to the concept of single parameter optimization is bicriteria optimization, where given two objective functions, the aim is to find a solution that optimizes the first, while maintaining a restriction on the second. The concept of approximation is generalized to these problems in a two-fold

manner: An approximate solution is sought, such that it is a factor \gamma away from an optimum respecting the restriction in terms of the optimized objective function, and it is a factor \delta away from satisfying the restriction on the other function. Such a solution is said to be a (\delta,\gamma)-approximation.

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))-approximation, i.e. the solution is guaranteed to port a profit of at least a fraction of 1/O(log n) of the optimum respecting the budget, while it's cost can be at most twice the given budget. We extend these results and present a bicriteria tradeoff that, given an \eps \in (0,1], guarantees a (1+\eps,O(log n)/\eps)-approximation.