Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Maximizing Symmetric Submodular Functions
 
research article

Maximizing Symmetric Submodular Functions

Feldman, Moran  
2017
Acm Transactions On Algorithms

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by current research, unlike similar minimization problems that have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state-of-the-art approximation for general submodular functions. We first consider the problem of maximizing a non-negative symmetric submodular function f : 2(N) -> R+ subject to a down-monotone solvable polytope P subset of 0,1 . For this problem, we describe an algorithm producing a fractional solution of value at least 0.432 . f(OPT), where OPT is the optimal integral solution. Our second result considers the problem max{f(S) : vertical bar S vertical bar = k} for a non-negative symmetric submodular function f : 2(N) -> R+ For this problem, we give an approximation ratio that depends on the value k/vertical bar N vertical bar and is always at least 0.432. Our method can also be applied to non-negative non-symmetric submodular functions, in which case it produces 1/e - o(1) approximation, improving over the best-known result for this problem. For unconstrained maximization of a 11011-negative symmetric submodular function, we describe a deterministic linear-time 1/2-approximation algorithm. Finally, we give a [1 - (1 - 1/k)(k-1)]-approximation algorithm for Submodular Welfare with k players having identical non-negative submodular utility functions and show that this is the best possible approximation ratio for the problem.

  • Details
  • Metrics
Type
research article
DOI
10.1145/3070685
Web of Science ID

WOS:000408666100010

Author(s)
Feldman, Moran  
Date Issued

2017

Publisher

Association for Computing Machinery

Published in
Acm Transactions On Algorithms
Volume

13

Issue

3

Start page

39

Subjects

Symmetric submodular functions

•

cardinality constraint

•

matroid constraint

•

submodular welfare

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Available on Infoscience
October 9, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/141298
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés