M.Sc Thesis

M.Sc StudentFlysher Guy
SubjectApproximation Algorithms for Partial Capacitated
Covering Problems
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Reuven Bar-Yehuda
Full Thesis textFull thesis text - English Version


We study the partial capacitated vertex cover problem (pcvc) in which the input consists of a graph $G$ and a covering requirement $L$.  Each edge $e$ in $G$ is associated with a demand (or load) $\ell(e)$, and each vertex $v$ is associated with a (soft) capacity $c(v)$ and a weight $w(v)$.  A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least $L$.  The weight of a solution is $\sum_v \alpha(v) w(v)$, where $\alpha(v)$ is the number of copies of $v$ required to cover the demand of the edges that are assigned to $v$.  The goal is to find a solution of minimum weight.

We consider three variants of pcvc.  In pcvc with separable demands the only requirement is that total demand of edges assigned

to $v$ is at most $\alpha(v) c(v)$.  In pcvc with inseparable demands there is an additional requirement that if an edge is assigned to $v$ then it must be assigned to one of its copies.  The third variant is the unit demands version.