Maximizing Symmetric Submodular Functions

DOI10.1007/978-3-662-48350-3_44zbMath1452.90262arXiv1409.5900OpenAlexW2619426625MaRDI QIDQ3452815

Moran Feldman

Publication date: 19 November 2015

Published in: ACM Transactions on Algorithms, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.5900

zbMATH Keywords

matroid constraintcardinality constraintsymmetric submodular functionssubmodular welfare

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (3)

A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Guess free maximization of submodular and linear sums ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum degree orderings
• Minimizing symmetric submodular functions
• Symmetry and Approximability of Submodular Maximization Problems
• Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
• Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Maximizing Non-monotone Submodular Functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Maximizing Symmetric Submodular Functions