Paper Info
Title
Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
Abstract
Given a graph G = (V ,E ) and a set R *** V ×V of requests, we consider to assign a set of edges to each node in G so that for every request (u , v ) in R the union of the edge sets assigned to u and v contains a path from u to v . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each node. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general R has ***(logn ) lower and upper bounds on approximation ratio under the assumption P *** NP , where n is the number of nodes in G . We then assume R forms a clique structure, called Subset-Full , which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes to be 2-approximable, though it has still no polynomial time approximation algorithm whose factor better than 677/676 unless P = NP . Finally, we show that this approximation ratio can be improved to 3/2 for undirected variant of MCD with Subset-Full.
Year
DOI
Venue
2009
10.1007/978-3-642-02882-3_7
COCOON
Keywords
Field
DocType
general r,request structures,polynomial time approximation algorithm,approximation ratio,minimum certificate dispersal problem,advanced investigation,request structure,assumption p,graph g,natural setting,set r
Discrete mathematics,Graph,Combinatorics,Clique,Cardinality,Mathematics,Polynomial time approximation algorithm,Certificate
Conference
Volume
ISSN
Citations 
5609
0302-9743
0
PageRank 
References 
Authors
0.34
10
4
Name
Order
Citations
PageRank
Tomoko Izumi114121.33
Taisuke Izumi228439.02
Hirotaka Ono340056.98
Koichi Wada431954.11