IJPAM: Volume 52, No. 5 (2009)
A POLYNOMIAL TIME ALGORITHM FOR MINIMIZING
A NONDECREASING SUPERMODULAR SET FUNCTION
AND ITS PERFORMANCE GUARANTEE
A NONDECREASING SUPERMODULAR SET FUNCTION
AND ITS PERFORMANCE GUARANTEE
Xiaoli Zhe
, Fangfang Zhang
, Wumin Wang
, Shanglu He
College of Mathematics, Physics and Software Engineering
Lanzhou Jiaotong University
Lanzhou, 730070, P.R. CHINA
e-mail: zhexl06@126.com





Lanzhou Jiaotong University
Lanzhou, 730070, P.R. CHINA

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