Submodular function maximization via the multilinear relaxation and contention resolution schemes

DOI10.1145/1993636.1993740zbMath1288.90081OpenAlexW1981351071MaRDI QIDQ5419149

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.649.5290

zbMATH Keywords

approximation algorithmmatroidsubmodular function maximizationcontention resolution schemeindependence constraint

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (37)

Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Matroid and knapsack center problems ⋮ Maximizing Symmetric Submodular Functions ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Max-Cut Under Graph Constraints ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Unsplittable Flow on Trees ⋮ Submodular Stochastic Probing on Matroids ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Optimization with demand oracles ⋮ Geometric Packing under Nonuniform Constraints ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Stochastic block-coordinate gradient projection algorithms for submodular maximization ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Unnamed Item ⋮ Parametric monotone function maximization with matroid constraints ⋮ Unnamed Item ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Bulk-robust combinatorial optimization ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Robust monotone submodular function maximization ⋮ Approximation algorithms for the partition vertex cover problem ⋮ Generalized budgeted submodular set function maximization ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Approximation algorithms for the geometric firefighter and budget fence problems ⋮ Informative path planning as a maximum traveling salesman problem with submodular rewards ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: Submodular function maximization via the multilinear relaxation and contention resolution schemes