M.Sc Student M.Sc Thesis Flysher Guy Approximation Algorithms for Partial Capacitated Covering Problems Department of Computer Science PROFESSOR EMERITUS Reuven Bar-Yehuda

Abstract

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.