Automatic taxonomy generation: Issues and possibilities
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k ≥ 2 and any ε > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k + ε) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves upon the 1/(k + 1)-approximation of Fisher, Nemhauser, and Wolsey obtained in 1978 [Fisher, M., G. Nemhauser, L. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions-II. Math. Programming Stud. 8 73-87]. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general nonmonotone submodular function subject to k matroid constraints. We show that, in these cases, the approximation guarantees of our algorithms are 1/(k - 1 + ε) and 1/(k + 1 + 1/(k - 1) + ε), respectively. Our analyses are based on two new exchange properties for matroids. One is a generalization of the classical Rota exchange property for matroid bases, and another is an exchange property for two matroids based on the structure of matroid intersection. © 2010 INFORMS.
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
G. Ramalingam
Theoretical Computer Science
David S. Kung
DAC 1998
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997