\documentclass{crorr} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{1} \renewcommand\thisnumber{x} \renewcommand\thisyear {201x} \renewcommand\thisvolume{x} \renewcommand\datereceived{xx xx, 201x} \renewcommand\dateaccepted{yy yy, 201x} \renewcommand\dateavailable{zz zz, 201x} %%%%%%%% end journal info %%%%%%%%%%%%% %%%%% author macros %%%%%%%%% % place your own macros HERE %%%%% end %%%%%%%%% \newcommand\textcyr[1]{{\fontencoding{OT2}\fontfamily{wncyr}\selectfont #1}} \newcommand{\vect}[1]{\mathrm{\mathbf{#1}}} \newcommand{\vx}{\vect{x}} \newcommand{\vxhat}{\vect{\hat{x}}} \newcommand{\vy}{\vect{y}} \newcommand{\vyhat}{\vect{\hat{y}}} \newcommand{\vs}{\vect{s}} \newcommand{\vS}{\vect{S}} \newcommand{\vX}{\vect{X}} \newcommand{\vH}{\vect{H}} \newcommand{\vh}{\vect{h}} \newcommand{\va}{\vect{a}} \newcommand{\vv}{\vect{v}} \newcommand{\vu}{\vect{u}} \newcommand{\vb}{\vect{b}} \newcommand{\vc}{\vect{c}} \newcommand{\vC}{\vect{C}} \newcommand{\vp}{\vect{p}} \newcommand{\vP}{\vect{P}} \newcommand{\vw}{\vect{w}} \newcommand{\vB}{\vect{B}} \newcommand{\Ron}[1]{\mathrm{R}^{#1}} \newcommand{\vdx}{\vect{\Delta x}} \newcommand{\vdxhat}{\vect{\Delta \hat{x}}} \newcommand{\vdy}{\vect{\Delta y}} \newcommand{\vdyhat}{\vect{\Delta \hat{y}}} \newcommand{\vdxt}[1]{\vect{\Delta x}^{(#1)}} \newcommand{\vdxhatt}[1]{\vect{\Delta \hat{x}}^{(#1)}} \newcommand{\vdyt}[1]{\vect{\Delta y}^{(#1)}} \newcommand{\vdyhatt}[1]{\vect{\Delta \hat{y}}^{(#1)}} \newcommand{\vxt}[1]{\vect{x}^{(#1)}} \newcommand{\vxhatt}[1]{\vect{\hat{x}}^{(#1)}} \newcommand{\vyt}[1]{\vect{y}^{(#1)}} \newcommand{\vyhatt}[1]{\vect{\hat{y}}^{(#1)}} \newcommand{\vpt}[1]{\vect{p}^{(#1)}} \newcommand{\vphatt}[1]{\vect{\hat{p}}^{(#1)}} \newcommand{\vnull}{\vect{0}} \newcommand{\dokteo}{\noindent\textbf{Proof.} } \newcommand{\niceA}{\mathcal{A}} \newcommand{\vA}{\vect{A}} \newcommand{\proofend}{\hfill$\square$} \newcommand{\niceU}{\mathcal{U}} \newcommand{\niceS}{\mathcal{S}} \newcommand{\niceR}{\mathcal{R}} \newcommand{\niceN}{\mathcal{N}} \newcommand{\niceG}{\mathcal{G}} \newcommand{\niceC}{\mathcal{C}} \newcommand{\niceO}{\mathcal{O}} \newcommand{\niceP}{\mathcal{P}} \newtheorem{fact}{Fact} \renewcommand{\thefact}{\arabic{fact}} %%%%%%%%% already loaded packages -- DO NOT RELOAD %%%%% % \usepackage{amssymb} % \usepackage{amsmath,amsthm} % \usepackage{latexsym} % \usepackage{amsfonts} % \usepackage{amsbsyt} % \usepackage{graphicx} %%%%%% end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{booktabs,ctable} %%Bibliografy Packages %\usepackage[sectionbib]{chapterbib} \usepackage{multirow} \usepackage{subfig} %%Table Packages \usepackage{algpseudocode,algorithmicx,algorithm} \usepackage{amstext,amsopn,amsbsy} \begin{document} \markboth{Slobodan Jeli\'c}{An FPTAS for the fractional group Steiner tree problem} \title{An FPTAS for the fractional group Steiner tree problem} \author[Names of authors]{\bf Slobodan Jeli\'{c}\affil{1}\comma \corrauth} \address{\affilnum{1} Department of Mathematics, Josip Juraj Strossmayer University of Osijek \\ Trg Ljudevita Gaja 6, Osijek, Croatia\\ E-mail: $\langle$ sjelic@mathos.hr $\rangle$ } %%%%% Begin Abstract %%%%%%%%%%% \begin{abstract} This paper considers a linear relaxation of the cut-based integer programming formulation for the group Steiner tree problem (FGST). We combine an approach of Koufogiannakis and Young (2013) with the nearly-linear time approximation scheme for the minimum cut problem of Christiano et. al (2011) in order to develop a fully polynomial time approximation scheme for FGST problem. Our algorithm returns the solution to FGST whose objective function value is at most $1+6\varepsilon$ times the optimal, for $\varepsilon\in\langle0,1/6]$, in $\tilde{O}(mk(m+n^{4/3}\varepsilon^{-16/3})/\varepsilon^2)$ time, where $n$, $m$ and $k$ are the numbers of vertices, edges and groups in the group Steiner tree instance, respectively. This algorithm has a better worst-case running time than the previous one in Garg and Khandekar (2002) when the number of groups is large enough. \end{abstract} %%%%% end %%%%%%%%%%% %%%%% Keywords %%%%%%%%%%% \keywords{approximation algorithm, fully polynomial time approximation scheme, Lagrangean relaxation, group Steiner tree problem, fractional group Steiner tree problem , covering linear program, packing linear program} %%%% maketitle %%%%% \maketitle %%%% Start %%%%%% \bigskip \noindent \section{Introduction} \textbf{Problem definition.} The group Steiner tree (GST) problem was introduced by Reich and Widmayer \cite{Reich:1990:BSP:88208.88252}, motivated by the problem of wire routing with multiport terminals in physical VLSI design. We are given an undirected graph $G=(V,E)$, $|V|=n$, $|E|=m$, with edge-weight function $w:E\rightarrow \mathbb{R}_+$, and a family of subsets of $V$, $\niceG=\{G_1,\ldots,G_k\}$, $k\in \mathbb{N}$, $G_i\neq \emptyset$ which are called \emph{groups}. The problem is to find a subtree $T$ such that $$\sum_{e\in E(T)}w(e)$$ is minimized and $V(T)\cap G_i\neq \emptyset$ for each $i\in [k]$. An instance of the group Steiner tree problem is denoted by $(G,\niceG,w)$. We consider the algorithm for the \textit{rooted version} where the pre-specified vertex $r$ is required to be in the solution subtree. Vertex $r$ is called a \textit{root}. In order to solve the unrooted version, we solve the rooted version for all vertices in the smallest group as possible choices for root $r$, and take the solution of the smallest weight. Let $\niceS_{r}=\bigcup_{i=1}^k\{S\subseteq V\setminus\{r\}:G_i\subseteq S\}$ be a family of all subsets $S$ of $V\setminus\{r\}$ such that the cut $(S,V\setminus S)$ separates some group $G_i$ from the pre-specified root $r$ and $\delta(S)=\{\{s,t\}\in E: s\in S, t\notin S\}$. We are ready to give a \textit{natural cut-based integer programming formulation} of this problem : \begin{equation}\label{eq::018} \begin{array}{rcrcl} &\mathrm{min}&\sum_{e\in E}w(e)z_e&&\\ &&&&\\ s.t.&&\sum_{e\in \delta(S)}z_e&\geq&1,\quad S\in \niceS_r, \\ &&z_e&\in& \{0,1\},\quad e\in E. \end{array} \end{equation} In this paper, we consider a relaxed version of Problem (\ref{eq::018}) where the integrality constraints $z_e\in\{0,1\}$, $e\in E$ are replaced by non-negativity constraints $z_e\geq 0$, $e\in E$, \begin{equation}\label{eq::019} \begin{array}{rcrcl} &\mathrm{min}&\sum_{e\in E}w(e)z_e&&\\ &&&&\\ s.t.&&\sum_{e\in \delta(S)}z_e&\geq&1,\quad S\in \niceS_r, \\ &&z_e&\geq& 0,\quad e\in E. \end{array} \end{equation} The LP Problem (\ref{eq::019}) is called the \emph{fractional group Steiner tree problem} (FGST). We give an interpretation in terms of a flow network by adding new vertices and using the max-flow min-cut theorem. Let us assume we introduce a new vertex $g_i$ for each group $G_i$ and a directed edge from $g_i$ to each vertex $v\in G_i$ with infinite capacity. The value of variable $z_e$ is interpreted as the capacity of edge $e$. Conditions in (\ref{eq::018}) ensure that the capacity of each cut separating some group $G_i$ from root $r$ (or equivalently, some $g_i$ from $r$) is at least one. Using max-flow min-cut theorem, it is easy to see that capacities $z_e$ are sufficient to send at least one unit of flow from each vertex $g_i$ to root $r$. \textbf{Motivation and related problems.} The group Steiner tree problem generalizes two important problems: The Steiner tree problem and the set cover problem. The Steiner tree problem is one of the most important NP-hard problems in combinatorial optimization that admits an approximation algorithm with constant approximation ratio \cite{Byrka2010,Byrka2013}. Actually, it is NP-hard to approximate it within a ratio of less then $96/95$ \cite{Chlebik2008}. In the Steiner tree problem, we are given an undirected graph $G=(V,E)$, $|V|=n$, $|E|=m$, with edge-weight function $w:E\rightarrow \mathbb{R}_+$ and subset of vertices $\emptyset\neq R\subseteq V$ that are called \emph{terminals}. Vertices in $V\setminus R$ are called \emph{Steiner vertices}. The task is to find a minimum-weight subtree $T$ that spans all terminals. It is easy to observe that the Steiner tree problem is reducible to a special case of GST problem where the size of each group is at most one. The set cover problem is the second one, but not less important since it generalizes a number of other combinatorial problems. We are given a set of elements $U$ and a family $\niceU$ of subsets of $U$ such that $\bigcup_{S\in \niceU}=U$. We say that subfamily $\niceR\subseteq\niceU$ is a set cover with respect to the instance $(U,\niceU)$ if every $u\in U$ is covered by at least one set from $\niceR$. The \emph{set cover problem} introduced by Karp \cite{Karp1972} is to find a subfamily $\niceR$ of minimum size. The more general version of the problem is typically called the \emph{weighted set cover problem} where each set from family $\niceU$ has a nonnegative weight associated with it. It is known that the set cover problem cannot be approximated by an approximation ratio better than $(1-o(1))\ln n$, unless NP contains slightly superpolynomial time algorithms \cite{Feige1998}. For a given set cover instance $(U,\niceU)$ we construct the star graph whose leaves are associated with sets in $\niceU$. Each element in $U$ defines a group. Each vertex belongs to groups that correspond to the elements contained in the set associated with that leaf. The weight of each leaf is equal to the weight of the set associated with it. We have just described the reduction of the set cover problem to GST problem. Indeed, algorithms for this problem can be used to solve some other related problems \cite{Elbassioni2012}. Solving the LP relaxation of the problem is a very common first step in combinatorial optimization algorithms. Particularly, if we look at the polylogarithmic approximation algorithm for GST given by Garg et al. \cite{Garg2000}, we see that it solves (\ref{eq::019}) when the input graph is a tree. Afterwards, they extend their result to general graphs using Bartal's technique of tree metrics approximation \cite{Bartal1998,Fakcharoenphol2004}. Fortunately, it is not necessary to solve (\ref{eq::019}) to optimality, but it is enough to find $(1+O(\varepsilon))$-approximate solution to (\ref{eq::019}) for some small $\varepsilon>0$. We refer to their theorem. \begin{theorem}[Garg et al. \cite{Garg2000}, page 75, Theorem 4.1.]\label{theo::001} There is a randomized polynomial time algorithm that, with the probability at least $1/2$, finds a group Steiner tree on an underlying graph which is a tree, of cost no more than $O(\log N\log k)$ times optimal value of FGST in (\ref{eq::019}), where $N$ is the maximum size of group and $k$ is the number of groups. \end{theorem} Indeed, the polylogarithmic approximation ratio given by Garg et al. gives an upper bound on the integrality gap of the relaxation in (\ref{eq::019}). It is not hard to observe that approximating (\ref{eq::019}) within a factor $1+O(\varepsilon)$, for some small $\varepsilon>0$, does not asymptomatically change the approximation ratio in Theorem \ref{theo::001}. It motivates us to find an efficient \textit{fully polynomial time approximation scheme} (FPTAS) for (\ref{eq::019}). We say that some algorithm for a minimization problem is FPTAS if it returns a solution whose cost is at most $1+\varepsilon$ times the cost of the optimal, for arbitrarily small $\varepsilon>0$, in time that is polynomial in the input size of the problem and $1/\varepsilon$. \section{Previous work} The paper by Garg and Khandekar \cite{Garg2002} considers the fractional Steiner Forest and some related problems. Their approach leads to an unified framework for finding a minimum hitting set for a collection of \textit{clutters}. A clutter on set $X$ is a family $\niceC$ of subsets of $X$ such that no set in $\niceC$ is contained in some other set in $\niceC$. We say that clutter $\niceC$ is hit by $T\subset X$ if at least one of its sets is included in $T$. Their algorithm aims to find a minimum cost subset $T$ of $X$ that hits each clutter in the family of $k$ clutters $\niceC_1,\ldots,\niceC_k$ on $X$. Their approach also uses an oracle $\niceO_i$, $i\in [k]$, that computes the minimum cost set in clutter $C_i$ and runs in time $T_{\niceO_i}$. All problems they consider can be formulated as the above described \emph{min-hit problem}. They give $(1+\varepsilon)$-approximation of the optimal solution of the min-hit problem in $O((m\log^2 k)/\varepsilon^2\sum_{i=1}^kT_{\niceO_i})$ time. FGST can be easily interpreted as a min-hit problem on a collection of clutters $\{\niceP_i\}_{i=1}^k$ on the set of edges $E$. Each clutter $\niceP_i$, $i\in[k]$ consists of paths from group $G_i$ (i.e. some vertex from group $G_i$) to the root $r$. We wish to find a minimum cost subset of edges that hits each clutter $\niceP_i$, $i\in [k]$. In this case, all oracles $\niceO_i$, $i\in [k]$ are the shortest path algorithms from vertices in $G_i$ to $r$. Since the root $r$ is fixed, $\niceO_i$ takes as much time as it is taken by a single-source shortest path algorithm. We conclude that the algorithm by Garg and Khandekar in \cite{Garg2002} runs in $O(mk(m + n\log n)\log^2 k/\varepsilon^2)$ time\footnote{$\tilde{O}(f(n))$ denotes $O(f(n)\log^cf(n))$ for some function $f$ and positive constant $c$}. They pointed out that their algorithm is the only one known for families of clutters that do not satisfy max-flow min-cut (MFMC) property. According to their approach, group Steiner tree problem can be viewed as the min-hit problem on family of clutters that consist of multicommodity paths. \section{FPTAS improvements} Although FGST has a compact flow-based formulation with polynomially many variables and constraints \cite{Halperin2007}, combinatorial algorithms exploiting the special structure of a problem have often better worst-case running time bounds than some known algorithms for general linear programming problems. The linear program (\ref{eq::019}) has the structure of a fractional covering linear program that is more carefully studied later in the paper. Since (\ref{eq::019}) has exponentially many constraints, state-of-the-art approaches in \cite{Koufogiannakis2007,Koufogiannakis2013a,Jelic2014} cannot be directly applied. Our main task is to adopt their approach and show that it yields a better worst case running time algorithm compared to the previous algorithms, when the number of groups $k$ is large enough. Garg and Khandekar in \cite{Garg2002} pointed out that techniques in \cite{Plotkin1995,Young2001} cannot be applied to obtain a FPTAS for the min-hit problem on a collection of clutters since it cannot be formulated as a packing or covering problem. First, we want to present that nearly linear-time FPTAS for explicit fractional packing and covering linear programs by Koufogiannakis and Young in \cite{Koufogiannakis2013a} is adoptable to an FPTAS for the FGST problem. This adaptation is very similar to the algorithm given by Garg and K\"onemann in \cite{Garg1998,Garg1998c} for maximum multicommodity flow problem and other fractional packing problems. Second, we point that the running time of our algorithm is $O((m\log m)k(m+n^{4/3}\varepsilon^{-16/3})\log^c(m+n^{4/3}\varepsilon^{-16/3})/\varepsilon^2)$ where $c$ is some constant that comes from running time of $(1+\varepsilon)$-approximate min-cut algorithm in \cite{Christiano2011} (Theorem \ref{theo::002}). If we neglect constants in running times, finding a (sub)set of solutions of the following inequality: \begin{align}\label{eq::016} \frac{m\log^2 k}{\varepsilon^2}k(m + n\log n) &> \frac{m\log m}{\varepsilon^2}k(m+n^{4/3}\varepsilon^{-16/3})\log^c(m+n^{4/3}\varepsilon^{-16/3}), \end{align} gives us a values of $k$ that make our algorithm faster than algorithm in \cite{Garg2002}. Now, we give a following technical facts that simplify the lower bound on values of $k$ which satisfy (\ref{eq::016}). \begin{fact}\label{prop::002} \begin{itemize} \item[]{} \item[i)]{ For any $\varepsilon\in\langle0,1\rangle$, there is a $n_0\in \mathbb{N}$ such that $$\frac{m+n^{4/3}\varepsilon^{-16/3}}{m + n\log n}<\frac{n^{1/3}}{\log n}\varepsilon^{-16/3},$$ for all $n\geq n_0$ and $n-1\leq m\leq n(n-1)/2$. } \item[ii)] For any constant $c$ and $\varepsilon\in\langle0,1/6]$ there is a $n_0\in \mathbb{N}$ such that $$\frac{n^{1/3}}{\log n}>\log^c(m+n^{4/3}\varepsilon^{-16/3}),$$ for all $n\geq n_0$ and $n-1\leq m\leq n(n-1)/2$. \end{itemize} \end{fact} Now, from (\ref{eq::016}) follows that \begin{equation}\label{eq::017} \log^2 k > \frac{m+n^{4/3}\varepsilon^{-16/3}}{m + n\log n}\log m\log^c(m+n^{4/3}\varepsilon^{-16/3}). \end{equation} Fact (\ref{prop::002}) implies the following bound on the right-hand side of (\ref{eq::017}) \begin{equation}\label{eq::022} \frac{m+n^{4/3}\varepsilon^{-16/3}}{m + n\log n}\log m\log^c(m+n^{4/3}\varepsilon^{-16/3})< \left(\frac{n^{1/3}}{\log n}\right)^2\varepsilon^{-16/3}, \end{equation} for $n\geq n_0$ and some $n_0\in \mathbb{N}$. In order to identify some values of $k$ that satisfy (\ref{eq::016}), inequalities (\ref{eq::017}) and (\ref{eq::022}) suggest that it is sufficient to find $k$ such that: \begin{equation} \log^2 k>\left(\frac{n^{1/3}}{\log n}\right)^2\varepsilon^{-16/3}, \end{equation} which gives \begin{equation}\label{eq::023} k>2^{\left(\frac{n^{1/3}}{\log n}\right)\varepsilon^{-8/3}}, \end{equation} for $n\geq n_0$ and some $n_0\in \mathbb{N}_0$. Now, we can conclude that our algorithm from Theorem \ref{theo::002} is faster that the algorithm in \cite{Garg2002} when $k>2^{(n^{1/3}/\log n)\varepsilon^{-8/3}}$ and $n\geq n_0$, for some $n_0\in\mathbb{N}$. Our approach is independent of approximate minimum cut computation in Algorithm \ref{alg::002}. Some newer and faster nearly linear algorithms \cite{Sherman2013} also can be used, but all incoming improvements of approximate max-flow min-cut computation will only decrease the lower bound (\ref{eq::023}). Unfortunately, improvements of approximate min-cut computation cannot significantly improve the running time of Algorithm \ref{alg::001} by decreasing dominating polynomial factors. In Section 2 we give an essential overview of the Lagrangean relaxation algorithm given by Koufogiannakis and Young \cite{Koufogiannakis2007,Koufogiannakis2013a} based on the idea of a two players zero-sum game \cite{Grigoriadis1995} and non-uniform increments \cite{Garg1998,Garg1998c}. In the spirit of their algorithm, we present an adaptation that involves calling of an oracle routine that computes a $(1+\varepsilon)$-approximate cut at each iteration. In Section 3, the analysis of the approximation ratio and running time is given. \subsection{Preliminaries} In order to present the main idea of our approach, let us recall the covering and packing linear programs as it is considered in \cite{Koufogiannakis2013a}. Let $\vA\in\mathbb{R}^{m\times n}_+$, $\vc\in\mathbb{R}^{n}_+$ and $\vb\in \mathbb{R}^{m}_+$ for $m,n\in \mathbb{N}$. The linear program \begin{equation}\label{eq::001} \begin{array}{rcrcl} &\mathrm{min}&\vc^T\vx&&\\ &&&&\\ s.t.&&\vA\vx&\geq&\vb, \\ &&\vx&\geq& \vnull, \end{array} \end{equation} is called a \textbf{covering linear program}. The dual of (\ref{eq::001}) \begin{equation}\label{eq::002} \begin{array}{rcrcl} &\mathrm{max}&\vb^T\vy&&\\ &&&&\\ s.t.&&\vA^T\vy&\leq&\vc, \\ &&\vy&\geq& \vnull \end{array} \end{equation} is called a \textbf{packing linear program}. W.l.o.g we assume that components of vectors $\vb$ and $\vc$ are all ones. After transformation of Problem (\ref{eq::019}), we obtain the following fractional covering program \begin{equation}\label{eq::020} \begin{array}{rcrcl} &\mathrm{min}&\sum_{e\in E}x_e&&\\ &&&&\\ s.t.&&\sum_{e\in \delta(S)}\frac{1}{w(e)}x_e&\geq&1,\quad S\in \niceS_r, \\ &&x_e&\geq& 0,\quad e\in E, \end{array} \end{equation} while the dual is the fractional packing linear program \begin{equation}\label{eq::004} \begin{array}{rcrcl} &\mathrm{max}&\sum_{S\in \niceS_r}y_S&&\\ &&&&\\ s.t.&&\sum_{S\in \niceS_{r,e}}\frac{1}{w(e)}y_S&\leq&1,\quad e\in E, \\ &&y_S&\geq& 0,\quad S\in \niceS_{r}, \end{array} \end{equation} where $\niceS_{r,e}=\{S\in \niceS_r: e\in \delta(S)\}$. Now it is clear that (\ref{eq::020}) and (\ref{eq::004}) are representable in the form of (\ref{eq::001}) and (\ref{eq::002}), respectively, where matrix $\vA$ is given by \begin{equation} A_{S,e}=\left\{\begin{array}{rcl} 1/w(e)&,&e\in\delta(S),\\ 0&,&\mbox{otherwise}. \end{array}\right. \end{equation} %For $\vx\in \mathbb{R}$, $|\vx|$ denotes the $1$-norm of the vector $\vx$. \subsection{Algorithm} \subsubsection{Description of the algorithm} We present the Lagrangian relaxation algorithm based on ideas described in the papers of Koufogiannakis and Young \cite{Koufogiannakis2007,Koufogiannakis2013a} that iteratively improves the solution of the Primal (\ref{eq::020}). In order to present the main idea of the algorithm, we recall how to obtain a Lagrangian relaxation of the Dual (\ref{eq::004}) \begin{align}\label{eq::021} \max_{\vA^T \vy \leq \vect{1},\vy\geq \vnull}\vect{1}^T\vy&\leq \min_{\vx\geq \vnull}\max_{\vy\geq \vnull}\left(\vect{1}^T\vy+\vx^T(\vect{1}-\vA^T\vy)\right). \end{align} Let $\tilde{y}_e(t)$ be $\sum_{S\in \niceS_{r,e}}y_S(t)/w(e)$, for $e\in E$. We conclude in (\ref{eq::021}) that the primal variable $x_e$ plays the role of the penalty for the violation of the dual constraint $\sum_{S\in \niceS_{r,e}}y_S/w(e)\leq 1$. Let $x_e(t)$, $e\in E$ and $y_S(t)$, $S\in \niceS_{r}$ be the primal and dual variables at iteration $t\geq 0$. At the beginning, we have $x_e(0)=0$, $e\in E$ and $y_S(0)=0$, $S\in \niceS_{r}$. If $\tilde{y}_e(t)$ is "large", we suppose that the violation of the dual constraint is also "large". By (\ref{eq::021}) it is reasonable to increase $x_e$ in order to mimic the increasing of the penalty for the violation of the corresponding dual constraint. In order to quantify the violation, we use $\tilde{y}_e(t)$. Following the idea of exponential potential function methods in \cite{DanielBienstock487}, we increase each variable $x_e(t)$ by a quantity that is exponential in violation $\tilde{y}_e(t-1)$ divided by the sum of exponentials in all dual constraint violations. More precisely, our algorithm iteratively improves primal solution $x_e(t)$ by quantity that is proportional to $p_e(t)/|\vp(t)|$ where \begin{equation}\label{eq::007} p_e(t)=(1+\varepsilon)^{\tilde{y}_e(t-1)}. \end{equation} Instead of random sampling of the primal and dual variables, we deterministically increase one variable in the dual and all variables in the primal. At each iteration in line 13 of Algorithm \ref{alg::001}, we increment the dual variable $y_{\hat{S}(t)}$ by $\hat{W}(t)$, where $(\hat{S}(t),V\setminus\hat{S}(t))$ is the $(1+\varepsilon)$-approximate minimum cut with respect to the capacities $$c_e(t):= \frac{1}{w(e)}\frac{p_e(t)}{|\vp(t)|},\quad \mbox{ for }e\in E,$$ in graph $G$ that separates some group $G_i$ from $r$, and $\hat{W}(t):=\min_{e\in \delta(\hat{S}(t))}$ $w(e)$. More details about determining the cut $(\hat{S}(t),V\setminus\hat{S}(t))$ are available in Section \ref{sec::0202}. We also note, at line 11 of Algorithm \ref{alg::001}, that $\hat{W}(t)$ is the step length of increasing the primal variable $x_e$ in the direction $p_e(t)/|\vp(t)|$, for $e\in E$. In other words, $\hat{W}(t)$ is distributed among all primal variables according to the weight vector $p(t)/|\vp(t)|$. We also update $\tilde{y}_e(t)$ and $p_e(t)$ only for $e\in \delta(\hat{S}(t))$ at each iteration. Our algorithm terminates when $M(t)\geq T$ where \begin{equation}\label{eq::006} M(t):= \max_{e\in E}\tilde{y}_e(t). \end{equation} Scaling the primal solution $\vx$ by the capacity of the $(1+\varepsilon)$-approximate minimum cut gives a feasible primal solution. \begin{algorithm}[!h] \caption{FPTAS for fractional group Steiner tree problem}\label{alg::001} \begin{algorithmic}[1] \State $x_e(0):=0$, $\tilde{y}_e(0)=0$ for all $e\in E$, $y_S(0):=0$, $S\in \niceS_r$,$M(0)\gets 0$, $t:=0$, $T:=\frac{\ln m}{\varepsilon^2}$ \State $p_e(1):=1$, $e\in E$ \While{$M(t)M(t)$} \State $M(t)\gets \tilde{y}_e(t)$ \EndIf \Else \State $\tilde{y}_e(t)\gets\tilde{y}_e(t-1)$ \State $p_e(t+1)\gets p_e(t)$ \EndIf \EndFor \EndWhile \State calculate $S'$ with respect to the capacities $\vx(t)$ using Algorithm \ref{alg::002} \State $m(t)\gets \sum_{e\in\delta(S')}x_e(t)$ \State \Return $\vx(t)/m(t)$ \end{algorithmic} \end{algorithm} \subsubsection{$(1+\varepsilon)$-approximate minimum cut oracle}\label{sec::0202} In this section we describe the algorithm that computes a $(1+\varepsilon)$-approximate minimum cut $(\hat{S}(t),V\setminus\hat{S}(t))$ that separates some group $G_i$ from $r$ with respect to the capacities $c_e(t)$, $e\in E$, at iteration $t\geq 0$. We solve that problem as a sequence of $k$ $(1+\varepsilon)$-approximate minimum cut problems in the following group Steiner network. \begin{definition}\label{def::001} Let $(G,\niceG,w)$ be a group Steiner tree instance and $i\in [k]$. A group Steiner network with respect to the capacities $\vc\in \mathbb{R}_+^{|E|}$ is the network $(\vec{G}_i,\vc)$ where $\vec{G}_i$ is a directed graph obtained from $G$ as follows: \begin{itemize} \item for each edge $e=\{u,v\}\in E$, we introduce two directed edges $(u,v)$ and $(v,u)$ where each of them has the capacity $c_e$, \item for group $G_i\in \niceG$, we introduce a new vertex $g_i$, \item for each $v\in G_i$, we introduce a directed edge $(g_i,v)$ with infinite capacity. \end{itemize} \end{definition} At each iteration $l$ we compute a $(1+\varepsilon)$-approximate minimum cut that separates group $G_l$ and the root $r$ in the group Steiner network $(\vec{G}_l,\vc)$ by using the algorithm of Christiano et al. in \cite{Christiano2011}. At the end we take the one with minimum capacity. It is easy to see that we computed a $(1+\varepsilon)$-approximate cut that separates group $G_j$ from $r$, for some $j\in [k]$. The running time of Algorithm \ref{alg::002} is given in the following Proposition. \begin{proposition}\label{prop::0302} Algorithm \ref{alg::002} returns $\hat{S}\subseteq V\setminus \{r\}$, where $(\hat{S},V\setminus\hat{S})$ is $(1+\varepsilon)$-approximate min-cut that separates some group $G_i$ from $r$, in $\tilde{O}(k(m+n^{4/3}\varepsilon^{-16/3}))$ time. \end{proposition} \dokteo The construction of the group Steiner network in Definition \ref{def::001} does not asymptotically enlarge the size of the network because only one vertex is added and at most $2m+n$ directed edges are introduced\footnote{since each group contains at most $n$ vertices}. Therefore each computation of $(1+\varepsilon)$-approximate min-cut takes at most $\tilde{O}(m+n^{4/3}\varepsilon^{-16/3})$ time. Since there are $k$ such computations, the statement follows easily.\proofend \begin{algorithm} \caption{$(1+\varepsilon)$-approximate min-cut oracle}\label{alg::002} \begin{algorithmic} \State \textbf{Input:} the capacities $\vc$, $\varepsilon>0$ \State \textbf{Output:} $(1+\varepsilon)$-approximate min-cut $\hat{S}$ that separates $g_i$ from $r$ in the $(\vec{G}_i,\vc)$ for some $i\in[k]$ \State $\hat{C},\hat{C}'\gets \infty$ \State $\hat{S},\hat{S}'\gets \emptyset$ \For{$l=1,\ldots,k$} \State compute a $(1+\varepsilon)$-approximate $(g_l,r)$ min-cut $\hat{S}'$ in the network $(\vec{G}_l,\vc)$ by using algorithm in \cite{Christiano2011} \State $\hat{C}'\gets\sum_{e\in \delta(\hat{S}')}c(e)$ \If{$\hat{C}'<\hat{C}$} \State $\hat{S}\gets \hat{S}'$ \State $\hat{C}\gets \hat{C}'$ \EndIf \EndFor \State \Return $\hat{S}$ \end{algorithmic} \end{algorithm} %$$\vA=\left{\begin{array}{rcl} % % \end{array}\right.$$ \section{Analysis of the Algorithm \ref{alg::001}} In this section we prove that Algorithm \ref{alg::001} returns a feasible solution to (\ref{eq::019}) whose total cost is at most $1+O(\varepsilon)$ times optimal. We also prove that the running time is indeed the one that is previously mentioned in Section 3. \subsection{Approximation ratio analysis} First, we give some technical facts without proof that are necessary for an analysis. \begin{claim}\label{claim::001} \begin{itemize} \item[] \item[i)] $(1+\varepsilon)^x\leq 1+\varepsilon x$, for all $0<\varepsilon<1$ and $0\leq x\leq 1$ \item[ii)] $(1+\varepsilon x)\leq e^{\varepsilon x}$, for all $\varepsilon,x\in\mathbb{R}$ \end{itemize} \end{claim} In order to prove that Algorithm \ref{alg::001} returns $(1+O(\varepsilon))$-approximate solution to (\ref{eq::019}), we give some useful facts. \begin{proposition}\label{prop::001} For all $t\geq 1$ Algorithm \ref{alg::001} maintains the following invariants: \begin{itemize} \item[i)] $|\vx(t)|=|\vy(t)|$, $t\geq 0$ \item[ii)] $\max_{e\in E}(\tilde{y}_e(t)-\tilde{y}_e(t-1))=1$ \end{itemize} \end{proposition} \dokteo \\ \textit{i)} This statement follows easily from the facts that only one dual variable corresponding to $\hat{S}(t)$ is increased by $\hat{W}(t)$ and that the sum of all increments in primal variables equals $\hat{W}(t)$.\\ \noindent\textit{ii)} \begin{align*} \max_{e\in E}(\tilde{y}_e(t)-\tilde{y}_e(t-1))&=\max_{e\in E}\sum_{S\in\niceS_{r,e}}\frac{1}{w(e)}(y_S(t)-y_S(t-1))\\ &=\max_{e\in \delta(\hat{S}(t))}\frac{1}{w(e)}(y_{\hat{S}(t)}(t)-y_{\hat{S}(t)}(t-1))\\ &=\max_{e\in \delta(\hat{S}(t))}\frac{\hat{W}(t)}{w(e)}=\frac{\hat{W}(t)}{\min_{e\in \delta(\hat{S}(t))}w(e)}\\ &=1 \end{align*} \proofend The crucial fact in the analysis of the approximation ratio of Algorithm \ref{alg::001} is the upper bound on the value of $\Phi(t+1)$, where $\Phi$ is the potential function given by \begin{equation*}\label{eq::008} \Phi(t)=|\vp(t)|. \end{equation*} This approach is widely used in design of fast combinatorial approximation algorithms for similar problems. A very nice overview of potential function methods can be found in \cite{DanielBienstock487}. \begin{lemma}\label{lemma::001} For any $t\geq 1$ \begin{equation*} \Phi(t+1)\leq m\exp\left(\varepsilon\sum_{t'=1}^{t}\hat{W}(t')\hat{C}(t')\right), \end{equation*} where $\hat{C}(t)$ is the capacity of a $(1+\varepsilon)$-approximate minimum cut $(\hat{S}(t),V\setminus\hat{S}(t))$. \end{lemma} \dokteo \begin{align} \Phi(t+1)&=\sum_{e\in E}p_e(t+1)=\sum_{e\in E}(1+\varepsilon)^{\tilde{y}_e(t)}\notag\\ &=\sum_{e\in \delta(\hat{S}(t))}(1+\varepsilon)^{\tilde{y}_e(t-1)+\frac{\hat{W}(t)}{w(e)}}+\sum_{e\not\in \delta(\hat{S}(t))}(1+\varepsilon)^{\tilde{y}_e(t-1)}\notag\\ &=\sum_{e\in \delta(\hat{S}(t))}p_e(t)(1+\varepsilon)^{\frac{\hat{W}(t)}{w(e)}}+\sum_{e\not\in \delta(\hat{S}(t))}p_e(t)\label{eq::009} \end{align} From Fact $ii)$ in Proposition \ref{prop::001}, Claim \ref{claim::001} and (\ref{eq::009}) it follows \begin{align} \Phi(t+1)&\leq \sum_{e\in \delta(\hat{S}(t))}p_e(t)\left(1+\frac{\hat{W}(t)}{w(e)}\varepsilon\right)+\sum_{e\not\in \delta(\hat{S}(t))}p_e(t)\notag\\ &=|\vp(t)|\left(1+\varepsilon\sum_{e\in \delta(\hat{S}(t))}\frac{p_e(t)}{|\vp(t)|}\cdot\frac{\hat{W}(t)}{w(e)}\right)\notag\\ &=\Phi(t)\left(1+\varepsilon\sum_{e\in \delta(\hat{S}(t))}c_e(t)\hat{W}(t)\right)\notag\\ &\leq\Phi(t)\exp\left(\varepsilon\sum_{e\in \delta(\hat{S}(t))}c_e(t)\hat{W}(t)\right)\label{eq::010} \end{align} Iterating (\ref{eq::010}), we obtain the statement of the lemma \begin{align*} \Phi(t+1)&\leq \Phi(1)\exp\left(\varepsilon\sum_{t'=1}^{t}\sum_{e\in \delta(\hat{S}(t'))}c_e(t')\hat{W}(t')\right)\\ &=m\exp\left(\varepsilon\sum_{t'=1}^{t}\sum_{e\in \delta(\hat{S}(t'))}c_e(t')\hat{W}(t')\right)\\ &=m\exp\left(\varepsilon\sum_{t'=1}^{t}\hat{W}(t')\sum_{e\in \delta(\hat{S}(t'))}c_e(t')\right)\\ &=m\exp\left(\varepsilon\sum_{t'=1}^{t}\hat{W}(t')\hat{C}(t')\right). \end{align*} \proofend \begin{lemma}\label{lemma::002} Let $m(t)$ be $\min_{S\in \niceS_r}\sum_{e\in \delta(S)}\frac{x_e(t)}{w(e)}$, for $t\geq 1$, then $$\sum_{t'=1}^{t}\hat{C}(t')\hat{W}(t')\leq (1+\varepsilon)m(t).$$ \end{lemma} \dokteo Let us observe from line $11$ of Algorithm \ref{alg::001} that \begin{equation}\label{eq::011} x_e(t)=\sum_{t'=1}^t\hat{W}(t')\frac{p_e(t')}{|\vp(t')|}. \end{equation} For any arbitrary $S\in \niceS_r$ using (\ref{eq::011}) we have \begin{align} \sum_{e\in \delta(S)}\frac{x_e(t)}{w(e)}&=\sum_{e\in \delta(S)}\frac{1}{w(e)}\sum_{t'=1}^t\hat{W}(t')\frac{p_e(t')}{|\vp(t')|}\notag\\ &=\sum_{t'=1}^t\hat{W}(t')\sum_{e\in \delta(S)}\frac{1}{w(e)}\frac{p_e(t')}{|\vp(t')|}\notag\\ &=\sum_{t'=1}^t\hat{W}(t')\sum_{e\in \delta(S)}c_e(t'),\label{eq::012} \end{align} where $c_e(t')$ is given in line $6$ of Algorithm \ref{alg::001}. Since a $(1+\varepsilon)$-approximate minimum cut $(\hat{S}(t'),V\setminus\hat{S}(t'))$ is calculated at each iteration $t'$ with respect to the capacities $c_e(t')$, $e\in E$, from (\ref{eq::012}) it is obvious that \begin{equation*} (1+\varepsilon)\sum_{e\in \delta(S)}\frac{x_e(t)}{w(e)}\geq \sum_{t'=1}^t\hat{W}(t')\hat{C}(t'), \end{equation*} which proves the statement of the lemma.\proofend \noindent The following theorem gives the upper bound on the approximation ratio of Algorithm \ref{alg::001}. \begin{theorem} After termination, for any $\varepsilon\in\langle0,1/6]$, Algorithm \ref{alg::001} returns a $(1+6\varepsilon)$-approximate solution to the LP relaxation of the group Steiner tree (\ref{eq::020}). \end{theorem} \dokteo Statements of Lemmas \ref{lemma::001} and \ref{lemma::002} imply \begin{equation*} (1+\varepsilon)^{\tilde{y}_e(t)}\leq m\exp(\varepsilon(1+\varepsilon) m(t)),\quad \forall e\in E, \end{equation*} which, after taking the natural logarithm of both sides, becomes \begin{equation}\label{eq::013} \tilde{y}_e(t)\ln(1+\varepsilon)\leq \ln m + \varepsilon(1+\varepsilon) m(t),\quad \forall e\in E. \end{equation} Since inequality in (\ref{eq::013}) is valid for all $e\in E$, it follows that \begin{equation}\label{eq::014} M(t)\ln(1+\varepsilon)\leq \ln m + \varepsilon(1+\varepsilon) m(t),\quad \forall e\in E. \end{equation} Our algorithm terminates when inequality $M(t)\geq T$ is valid. If we use this fact in Inequality (\ref{eq::014}), we obtain \begin{equation*} \frac{m(t)}{M(t)}\geq 1-3\varepsilon, \end{equation*} which, for any $\varepsilon\in \langle0,1/6]$, gives \begin{equation}\label{eq::015} \frac{M(t)}{m(t)}\leq 1+6\varepsilon. \end{equation} Let $\hat{\vx}$ be the vector returned by Algorithm \ref{alg::001} and $\vx^{\ast}$ the optimal solution to (\ref{eq::020}). From Fact $i)$ in Proposition \ref{prop::001}, the strong duality theorem and (\ref{eq::015}), it follows that \begin{equation*} \frac{|\hat{\vx}|}{|\vx^{\ast}|}\leq \frac{\frac{|\vx|}{m(t)}}{\frac{|\vy|}{M(t)}}=\frac{M(t)}{m(t)}\leq 1+6\varepsilon. \end{equation*} \proofend \subsection{Running time analysis} In this section we give an analysis of the running time of Algorithm \ref{alg::001}. \begin{theorem}\label{theo::002} Algorithm \ref{alg::001} returns a $(1+6\varepsilon)$-approximate solution to (\ref{eq::020}) in\\ $\tilde{O}(mk(m+n^{4/3}\varepsilon^{-16/3})/\varepsilon^2)$ time. \end{theorem} \dokteo The update operations inside the while loop (lines 3-27), excluding line 8, in Algorithm \ref{alg::001} take $O(m)$ time. From Proposition \ref{prop::0302} it follows that Algorithm \ref{alg::001} takes $\tilde{O}(k(m+n^{4/3}\varepsilon^{-16/3}))$ time per iteration since Algorithm \ref{alg::002} runs inside the while loop at line 8 and it dominates the time of all update operations. It remains to show that there are at most $(m\ln m)/\varepsilon^2$ iterations until termination. There are at most $m$ iterations until $M(t)$ is increased by $1$ because at least one edge is a maximizer of left-hand side term in $ii)$ of Proposition \ref{prop::001}. It follows that $M(t)$ is at least $T$ after at most $mT$ iterations of the while loop.\proofend \section{Conclusion} We a presented simple modification of the fully polynomial time approximation scheme (FPTAS) in \cite{Koufogiannakis2007,Koufogiannakis2013a} for explicit fractional packing and covering linear programs that is very close to the approach in \cite{Garg1998,Garg1998c}. In such a way we obtained Algorithm \ref{alg::001} that computes a $(1+\varepsilon)$-approximate solution to the fractional group Steiner tree problem whose running time outperforms the algorithm in \cite{Garg2002} when the number of groups $k$ is large enough. Since all algorithms in \cite{Garg2002} for the min-hit problem on a family of clutters that do not satisfy the max-flow min-cut property are reported as the only ones known, further research in this area can be directed to improving the running times of these algorithms using an approach similar to the one presented in this paper. On the other side, the FPTAS for the fractional group Steiner tree (FGST) problem, that is presented in this paper, can be applied to approximate solving of large-scale group Steiner tree (GST) instances that naturally arise in operations research community. The FGST can be found as the part of approximation algorithms for GST problem \cite{Garg2000}. Furthermore, the solution of FGST problem can be used as a good lower bound on optimal solution to GST problem in some general linear integer programming techniques. Besides a very common application in the problem of wire routing with multiport terminals in physical VLSI design \cite{Reich:1990:BSP:88208.88252}, the GST problem can be applied to finding teams of experts in social networks that are supposed to solve some specific task \cite{Lappas2009,Anagnostopoulos2012,Li2015}. This application requires extremely fast algorithms since the social networks rapidly grow. This fact motivates a further improvements of running time of the FPTAS for the FGST problem. \section*{Acknowledgements} The author wishes to thank Domagoj Matijevi\'c for useful discussion. \begin{thebibliography}{} \bibitem[1]{Anagnostopoulos2012} Anagnostopoulos, A., Becchetti, L., Castillo, C., Gionis, A., and Leonardi, S. (2012). \newblock {Online team formation in social networks}. \newblock In { Proceedings of the 21st international conference on World Wide Web - WWW '12}, pages 839--848, New York, USA. ACM Press. \bibitem[2]{Bartal1998} Bartal, Y. (1998). \newblock {On approximating arbitrary metrices by tree metrics}. \newblock In { Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98}, pages 161--168, New York, USA. ACM Press. \bibitem[3]{DanielBienstock487} Bienstock, D. (2002). \newblock { Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice}. \newblock Springer. \bibitem[4]{Byrka2010} Byrka, J., Grandoni, F., Rothvo\ss, T., and Sanit\`{a}, L. (2010). \newblock {An improved LP-based approximation for Steiner tree}. \newblock In { STOC '10 Proceedings of the 42nd ACM symposium on Theory of computing}, pages 583--592, New York, USA. ACM Press. \bibitem[5]{Byrka2013} Byrka, J., Grandoni, F., Rothvoss, T., and Sanit\`{a}, L. (2013). \newblock {Steiner Tree Approximation via Iterative Randomized Rounding}. \newblock { Journal of the ACM}, 60(1):1--33. \bibitem[6]{Chlebik2008} Chleb\'{\i}k, M. and Chleb\'{\i}kov\'{a}, J. (2008). \newblock {The Steiner tree problem on graphs: Inapproximability results}. \newblock { Theoretical Computer Science}, 406(3):207--214. \bibitem[7]{Christiano2011} Christiano, P., Kelner, J.~A., Madry, A., Spielman, D.~A., and Teng, S.-H. (2011). \newblock {Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs}. \newblock { Proceedings of the 43rd annual ACM symposium on Theory of computing - STOC '11}, pages 273--282, New York, USA. ACM Press. \bibitem[8]{Elbassioni2012} Elbassioni, K., Jeli\'{c}, S., and Matijevi\'{c}, D. (2012). \newblock {The relation of Connected Set Cover and Group Steiner Tree}. \newblock { Theoretical Computer Science}, 438:96--101. \bibitem[9]{Fakcharoenphol2004} Fakcharoenphol, J., Rao, S., and Talwar, K. (2004). \newblock {A tight bound on approximating arbitrary metrics by tree metrics}. \newblock { Journal of Computer and System Sciences}, 69(3):485--497. \bibitem[10]{Feige1998} Feige, U. (1998). \newblock {A threshold of ln n for approximating set cover}. \newblock { Journal of the ACM}, 45(4):634--652. \bibitem[11]{Garg2002} Garg, N. and Khandekar, R. (2002). \newblock {Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems}. \newblock In { FOCS '02 Proceedings of the 43rd Symposium on Foundations of Computer Science}, pages 500--509. IEEE Computer Society. \bibitem[12]{Garg1998} Garg, N. and Konemann, J. (1998). \newblock {Faster and simpler algorithms for multicommodity flow and other fractional packing problems}. \newblock In { Proceedings 39th Annual Symposium on Foundations of Computer Science - FOCS'98}, pages 300--309, Palo Alto, CA, USA. IEEE Computer Society. \bibitem[13]{Garg1998c} Garg, N. and K\"{o}nemann, J. (2007). \newblock {Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems}. \newblock { SIAM Journal on Computing}, 37(2):630--652. \bibitem[14]{Garg2000} Garg, N., Konjevod, G., and Ravi, R. (2000). \newblock {A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem}. \newblock { Journal of Algorithms}, 37(1):66--84. \bibitem[15]{Grigoriadis1995} Grigoriadis, M.~D. and Khachiyan, L.~G. (1995). \newblock {A sublinear-time randomized approximation algorithm for matrix games}. \newblock { Operations Research Letters}, 18(2):53--58. \bibitem[16]{Halperin2007} Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., and Wang, N. (2007). \newblock {Integrality Ratio for Group Steiner Trees and Directed Steiner Trees}. \newblock { SIAM Journal on Computing}, 36(5):1494--1511. \bibitem[17]{Jelic2014} Jeli\'{c}, S., Laue, S., Matijevi\'{c}, D., and Wijerama, P. (2015). \newblock {A Fast Parallel Implementation of a PTAS for Fractional Packing and Covering Linear Programs}. \newblock { International Journal of Parallel Programming}, 43(5):840--875. \bibitem[18]{Karp1972} Karp, R.~M. (1972). \newblock {Reducibility among combinatorial problems}. \newblock In Miller, R.~E., Thatcher, J.~W., and Bohlinger, J.~D., editors, { Complexity of Computer Computations}, pages 85--103. Springer US. \bibitem[19]{Koufogiannakis2007} Koufogiannakis, C. and Young, N.~E. (2007). \newblock {Beating simplex for fractional packing and covering linear programs}. \newblock In { FOCS'07 Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science}, pages 494--504. IEEE. \bibitem[20]{Koufogiannakis2013a} Koufogiannakis, C. and Young, N.~E. (2013). \newblock {A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs}. \newblock { Algorithmica}. \bibitem[21]{Lappas2009} Lappas, T., Liu, K., and Terzi, E. (2009). \newblock {Finding a team of experts in social networks}. \newblock In { KDD '09 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining}, pages 467--176, New York, USA. ACM Press. \bibitem[22]{Li2015} Li, C.-T., Shan, M.-K., and Lin, S.-D. (2015). \newblock {On team formation with expertise query in collaborative social networks}. \newblock { Knowledge and Information Systems}, 42(2):441--463. \bibitem[23]{Plotkin1995} Plotkin, S.~A., Shmoys, D.~B., and Tardos, E. (1995). \newblock {Fast approximation algorithms for fractional packing and covering problems}. \newblock { Mathematics of Operations Research}, 20(2):257--301. \bibitem[24]{Reich:1990:BSP:88208.88252} Reich, G. and Widmayer, P. (1990). \newblock {Beyond Steiner's Problem: A VLSI Oriented Generalization}. \newblock In { Proceedings of the Fifteenth International Workshop on Graph-theoretic Concepts in Computer Science}, WG '89, pages 196--210, Springer-Verlag, New York, Inc. \bibitem[25]{Sherman2013} Sherman, J. (2013). \newblock {Nearly Maximum Flows in Nearly Linear Time}. \newblock In { 2013 IEEE 54th Annual Symposium on Foundations of Computer Science}, volume 2013, pages 263--269. IEEE Computer Society. \bibitem[26]{Young2001} Young, N. (2001). \newblock {Sequential and parallel algorithms for mixed packing and covering}. \newblock In { Proceedings 2001 IEEE International Conference on Cluster Computing}, pages 538--546. IEEE Computer Society. \end{thebibliography} \end{document}