M.Sc Thesis | |

M.Sc Student | Flysher Guy |
---|---|

Subject | Approximation Algorithms for Partial Capacitated Covering Problems |

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.