Optimization Online


Approximating the minimum directed tree cover

Viet Hung Nguyen (Hung.Nguyen***at***lip6.fr)

Abstract: Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover of minimum cost. The problem is known to be $NP$-hard. In this paper, we show that the weighted Set Cover Problem (SCP) is a special case of DTCP. Hence, one can expect at best to approximate DTCP with the same factor as for SCP. We show that this expectation can be satisfied in some way by designing a purely combinatorial approximation algorithm for the DTCP and proving that the approximation factor of the algorithm is $\max(2, \ln(D^+))$ with $D^+$ is the maximum outgoing degree of the nodes in $G$.

Keywords: approximation algorithms, tree cover, tour cover, set cover

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Integer Programming (0-1 Programming )

Citation: submitted

Download: [PDF]

Entry Submitted: 04/06/2010
Entry Accepted: 04/06/2010
Entry Last Modified: 06/16/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society