Record Details

A ROUNDING TECHNIQUE FOR THE POLYMATROID MEMBERSHIP PROBLEM

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A ROUNDING TECHNIQUE FOR THE POLYMATROID MEMBERSHIP PROBLEM
 
Creator NARAYANAN, H
 
Description We present an efficient technique for finding a subset which maximizes w(X) - rho(X) over all subsets of a set E, where w and rho are real modular and polymatroid functions respectively, using as a subroutine an algorithm which finds such a set for functions w, rho which are near w, rho respectively. In particular we can choose w, rho to be rational with denominators equal to 12[E](3) if we can assume, whenever rho(X) + rho(Y) > rho(X boolean OR Y) + rho(X boolean AND Y), that the difference between the two sides is at least one. By applying our technique, we construct an O(\E\(3)r(2)) algorithm for the case where rho is a matroid rank function.
 
Publisher ELSEVIER SCIENCE PUBL CO INC
 
Date 2011-07-27T13:46:27Z
2011-12-26T12:57:18Z
2011-12-27T05:47:23Z
2011-07-27T13:46:27Z
2011-12-26T12:57:18Z
2011-12-27T05:47:23Z
1995
 
Type Article
 
Identifier LINEAR ALGEBRA AND ITS APPLICATIONS, 221(), 41-57
0024-3795
http://dx.doi.org/10.1016/0024-3795(93)00222-L
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7240
http://hdl.handle.net/10054/7240
 
Language en