Title :
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
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;
Conference_Titel :
Computer Science and Service System (CSSS), 2011 International Conference on
Conference_Location :
Nanjing
Print_ISBN :
978-1-4244-9762-1
DOI :
10.1109/CSSS.2011.5972082
