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. Conferences, Workshops, Symposiums, and Seminars
  4. Maximizing Symmetric Submodular Functions
 
conference paper

Maximizing Symmetric Submodular Functions

Feldman, Moran  
Bansal, N
•
Finocchi, I
2015
Algorithms - Esa 2015
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases including cut functions of graphs and hypergraphs. In this work, we identify submodular maximization problems for which one can get a better approximation for symmetric objectives compared to what is known for general submodular functions. For 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, 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 is a 0.432-approximation algorithm for the problem max{f (S) vertical bar S vertical bar = k} with a non-negative symmetric submodular function f: 2(N) -> R+. Our method also applies to non-symmetric functions, in which case it produces 1/e -0(1) approximation. Finally, we describe a deterministic linear-time 1/2-approximation algorithm for unconstrained maximization of a non-negative symmetric submodular function.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-662-48350-3_44
Web of Science ID

WOS:000366210300046

Author(s)
Feldman, Moran  
Editors
Bansal, N
•
Finocchi, I
Date Issued

2015

Publisher

Springer Int Publishing Ag

Publisher place

Cham

Published in
Algorithms - Esa 2015
ISBN of the book

978-3-662-48350-3

978-3-662-48349-7

Total of pages

12

Series title/Series vol.

Lecture Notes in Computer Science

Volume

9294

Start page

521

End page

532

Subjects

Symmetric submodular functions

•

Cardinality constraint

•

Matroid constraint

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Event nameEvent placeEvent date
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference

Patras, GREECE

SEP 14-16, 2015

Available on Infoscience
February 16, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/123645
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