M.Sc Thesis

M.Sc StudentLanda Shimon
SubjectCombinatorial Approximation Algorithms for the Fractional
Set-Cover Problem
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor


Minimum (weight) set-cover is a well-known NP-hard optimization problem. It consists of a collection of m sets, each having a non-negative cost associated with it. The union of all the sets is denoted by U, whose cardinality is denoted by n. The goal is to find a minimum-cost sub-collection of the sets, whose union remains U. This work focuses on the fractional version of this problem, called fractional set-cover. It differs from the original problem as follows: the solution may pick each set to some fractional extent, while every element from U must still be covered, i.e., the summation of the fractions over all the sets to which the element belongs, is at least 1.

Muthukrishnan et al. present approximation algorithms for several optimization problems involving the rectangular partitioning of two-dimensional data. In this work, we show how their ideas and algorithms can be further developed and generalized into a new fast combinatorial (1+ ε)-approximation algorithm for the (weighted) fractional set-cover problem, for every ε > 0. More specifically, our generalization consists of the following:

  1. Solving general set-cover instances.

  2. Improving the approximation factor to (1+ ε), for every ε > 0.

  3. Generalizing to the weighted case of the problem.

  4. Generalizing to fractional optimization.

This algorithm constitutes our main result, and is described and analyzed in great detail. Moreover, we compare it to several other previously known combinatorial (1+ε)-approximation algorithms for the problem, highlighting how our approach, algorithm and analysis are fundamentally different (no exact combinatorial algorithm for the problem is known). Finally, we present applications of our main result to other optimization problems.