Submodular-function maximization subject to multiple constraints

Author

Zhao, Xingli ; Zhao, Cansheng ; He, Shanglu ; Wang, Wanxiong

Author_Institution

Sch. of Math., Phys. & Software Eng., Lanzhou Jiaotong Univ., Lanzhou, China

fYear

2011

fDate

27-29 June 2011

Firstpage

1754

Lastpage

1755

Abstract

Submodular-function maximization is a central and NP-hard problem in combinatorial optimization. The greedy algorithm are used in submodular-fuction maxization subject to multiple constraints. However, this paper present an improved local search algorithms and give the time complexity and performance analysis. Finally, it is shown that the algorithm is polynomial time approximate and has a relatively good time complexity.

Keywords

combinatorial mathematics; computational complexity; greedy algorithms; optimisation; search problems; NP-hard problem; combinatorial optimization; greedy algorithm; improved local search algorithms; multiple constraints; performance analysis; polynomial time approximation; submodular-function maximization; time complexity; Algorithm design and analysis; Approximation algorithms; Bismuth; Evolutionary computation; Greedy algorithms; Operations research; Performance analysis; Submodular-function; combinatoria loptimization; local search algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science and Service System (CSSS), 2011 International Conference on

Conference_Location

Nanjing

Print_ISBN

978-1-4244-9762-1

Type

conf

DOI

10.1109/CSSS.2011.5972082

Filename

5972082