IJPAM: Volume 52, No. 5 (2009)

A POLYNOMIAL TIME ALGORITHM FOR MINIMIZING
A NONDECREASING SUPERMODULAR SET FUNCTION
AND ITS PERFORMANCE GUARANTEE

Xiaoli Zhe$^1$, Fangfang Zhang$^2$, Wumin Wang$^3$, Shanglu He$^4$
$^{1,2,3,4}$College of Mathematics, Physics and Software Engineering
Lanzhou Jiaotong University
Lanzhou, 730070, P.R. CHINA
$^1$e-mail: zhexl06@126.com


Abstract.This paper presents a polynomial algorithm for minimizing a nondecreasing supermodular set function and discusses its performance guarantee.

Received: December 10, 2007

AMS Subject Classification: 05C15

Key Words and Phrases: polynomial algorithm, combinatorial optimization, supermodular set function, performance guarantee

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 52
Issue: 5