Submodular Maximization Through the Lens of Linear Programming

DOI10.1287/MOOR.2018.0965zbMATH Open1437.90096arXiv1711.11316OpenAlexW2965479381MaRDI QIDQ5108239FDOQ5108239

Authors: Simon Bruggmann, Rico Zenklusen 

Publication date: 30 April 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: The simplex algorithm for linear programming is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a constrained monotone submodular maximization problem yields a $1/2$-approximation, and we also present an appropriate extension to the non-monotone setting. However, reaching a local optimum quickly is a non-trivial task. Moreover, we describe a fast and very general local search procedure that applies to a wide range of constraint families, and unifies as well as extends previous methods. In our framework, we match known approximation guarantees while disentangling and simplifying previous approaches. Moreover, despite its generality, we are able to show that our local search procedure is slightly faster than previous specialized methods. Furthermore, we resolve an open question on the relation between linear optimization and submodular maximization; namely, whether a linear optimization oracle may be enough to obtain strong approximation algorithms for submodular maximization. We show that this is not the case by providing an example of a constraint family on a ground set of size $n$ for which, if only given a linear optimization oracle, any algorithm for submodular maximization with a polynomial number of calls to the linear optimization oracle will have an approximation ratio of only $O(frac1sqrtncdotfraclognloglogn)$.

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

Recommendations

• Maximizing submodular set functions subject to multiple linear constraints
• scientific article; zbMATH DE number 4137537
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Maximizing a class of submodular utility functions
• Maximization of submodular functions: theory and enumeration algorithms
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Techniques for submodular maximization
• Submodular functions: optimization and approximation

zbMATH Keywords

local searchapproximation algorithmshardness of approximationsubmodular function maximization

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial auctions with decreasing marginal utilities
• Improved approximations for \(k\)-exchange systems (extended abstract)
• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Submodular maximization over multiple matroids via generalized exchange properties
• On the complexity of approximating \(k\)-set packing
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Maximizing Non-monotone Submodular Functions
• A note on maximizing a submodular set function subject to a knapsack constraint
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Optimal approximation for the submodular welfare problem in the value oracle model
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Symmetry and approximability of submodular maximization problems
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Deterministic algorithms for submodular maximization problems
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Constrained submodular maximization via a nonsymmetric technique

Cited In (6)

• Sequence independent lifting for a set of submodular maximization problems
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Lexicographically Optimal Base of a Submodular System with respect to a Weight Vector
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Correction to: ``Guess free maximization of submodular and linear sums
• Note on pseudolattices, lattices and submodular linear programs

This page was built for publication: Submodular Maximization Through the Lens of Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108239)