Optimization Online


Simultaneous approximation of multi-criteria submodular function maximization

Donglei Du(ddu***at***unb.ca)
Li Yu(liyubjut***at***gmail.com)
Naihua Xiu(nhxiu***at***center.njtu.edu.cn)
Dachuan Xu(xudc***at***bjut.edu.cn)

Abstract: Recently there has been intensive interest on approximation of the NP-hard submodular maximization problem due to their theoretical and practical significance. In this work, we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization. We address existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric, respectively, along with algorithmic corollaries. We offer complete characterization of the symmetric case and partial results on the asymmetric case.

Keywords: Multi-criteria, submodular function maximization, approximation algorithm, existence

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Other Topics (Game Theory )

Citation: Working Paper Series 2012-005, University of New Brunswick, Canada

Download: [Postscript][PDF]

Entry Submitted: 03/31/2012
Entry Accepted: 04/01/2012
Entry Last Modified: 03/31/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society