Record Details

Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach
 
Creator NARAYANAN, H
ROY, S
PATKAR, S
 
Subject network
 
Description In this paper we discuss strategies for constructing approximation algorithms for solving the Min-k-cut problem, the Min-k-certex sharing problem, and their generalization the Min-k-overlap problem. In each case, we first formulate an appropriate submodular function and construct its principal lattice of partitions (PLP) (H. Narayanan, Linear Algebra Appl. 144 (1991), 179-216), Applying an elementary strategy on an appropriate subinterval of the PLP yields the approximation algorithms. We give two such strategies. For convenience and greater generality we present our results in terms of bipartite graphs (which may be regarded as representing hypergraphs). We observe that the Min-k-cut problem is NP-Hard (O. Goldschmidt and D. S. Hochbaum, in ''Proceeding 29th Annual Symposium on the Foundations of Computer Science.'' pp. 444-451, 1988). Approximation algorithms for the Min-k-cut problem were first given in (M. Saran and V. V. Vazirani, in ''Proceedings 32nd Annual Symposium on the Foundations of Computer Science, 1991''). Their algorithms yield a Min-k-cut which is at most 2(1 - (1/k)) times worse than the optimal. Our algorithm using the first strategy has a 2(1 - (1/n)) factor (times worse than optimal) for both Min-k-cut and Min-k-vertex sharing (1) problems (n is \V(G)\, \E(G)\ respectively). For Min-k-vertex sharing (2) this strategy yields a q(1 - (1/\E(G)\)) factor, where q is the maximum degree of a vertex in the graph G. Using a second strategy we are able to obtain a (2 - (k'/n')) factor for the Min-k-cut problem, where k' = k - k(0), n' = n - k(0), k(0) being an appropriate integer defined in the paper. In our approach the chief labor consists in finding a sequence of increasingly coarser partitions (starting with the partition into singleton blocks and ending with the single block partition of S) called the principal sequence. Once this is done the remaining effort is essentially O(\S\log S). (C) 1996 .
 
Publisher ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS
 
Date 2011-07-12T17:50:56Z
2011-12-26T12:49:01Z
2011-12-27T05:34:40Z
2011-07-12T17:50:56Z
2011-12-26T12:49:01Z
2011-12-27T05:34:40Z
1996
 
Type Article
 
Identifier JOURNAL OF ALGORITHMS, 21(2), 306-330
0196-6774
http://dx.doi.org/10.1006/jagm.1996.0047
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3403
http://hdl.handle.net/10054/3403
 
Language en