Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

DOI10.1137/110839655zbMath1437.90135OpenAlexW2094067695WikidataQ100368738 ScholiaQ100368738MaRDI QIDQ5112585

Rico Zenklusen, Jan Vondrák, Chandra Chekuri

Publication date: 31 May 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

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 (56)

Siting renewable power generation assets with combinatorial optimisation ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex -- ⋮ Measured continuous greedy with differential privacy ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Unnamed Item ⋮ Prophet Matching with General Arrivals ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ On the correlation gap of matroids ⋮ Towards an optimal contention resolution scheme for matchings ⋮ Distributed strategy selection: a submodular set function maximization approach ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Constrained stochastic submodular maximization with state-dependent costs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The multi-budget maximum weighted coverage problem ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Unnamed Item ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ A simple optimal contention resolution scheme for uniform matroids ⋮ Stochastic block-coordinate gradient projection algorithms for submodular maximization ⋮ Submodular Optimization with Contention Resolution Extensions. ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ The Submodular Secretary Problem Goes Linear ⋮ Adaptive robust submodular optimization and beyond ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Price of dependence: stochastic submodular maximization with dependent items ⋮ Approximating graph-constrained max-cut ⋮ Submodular unsplittable flow on trees ⋮ Stochastic submodular probing with state-dependent costs ⋮ Stochastic submodular probing with state-dependent costs ⋮ Approximating max-cut under graph-MSO constraints ⋮ Constrained submodular maximization via greedy local search ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Guess free maximization of submodular and linear sums ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Unnamed Item ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Contention resolution, matrix scaling and fair allocation ⋮ Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ 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