$b_v$. We show that the problem admits approximation ratio $H(d(V))+H(c(E))$.

author:
- Guy Kortsarz
- Zeev Nutov
title: |
    A unified approach to source location\
    via rooted network augmentation
---

Introduction
============

Problems considered and relations between them
----------------------------------------------

In this paper we suggest a unifying approach to handle [Source Location]{} problems via [Rooted Network Augmentation]{} problems. In [Source Location]{} problems the goal is to select a minimum cost source set $S$ such that the connectivity from $S$ to any other node $v$ is at least the demand $d_v$ of $v$. In [Network Augmentation]{} problems the goal is to augment a given graph by a minimum-cost edge-set such that the new graph satisfies prescribed connectivity requirements. Formally, the generic versions of these problems are as follows. Given a function $w=\{w_u:u \in U\}$ on a groundset $U$ and $U' \subseteq U$, let $w(U')=\sum_{u \in U'}w_u$. If $w$ is a cost function on $U$ and $I$ is an edge-set on $U$, then the cost (or the node-costs) $w(I)$ of $I$ is defined to be the cost of the set of the endnodes of $I$. Also, let $w_{\max}=\max_{u \in U} w_u$ denote the maximum value of $w$, and assume that all the input 