|M.Sc Student||Flysher Guy|
|Subject||Approximation Algorithms for Partial Capacitated|
|Department||Department of Computer Science||Supervisor||Professor Emeritus Reuven Bar-Yehuda|
|Full Thesis text|
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.