Submodular function maximization via the multilinear relaxation and contention resolution schemes

DOI10.1137/110839655MaRDI QIDQ5112585zbMATH OpenOpenAlexWikidataFDO

Authors Chandra Chekuri, Jan Vondrák, Rico Zenklusen

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

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

Recommendations

• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

Cited in

(86)

• Stochastic block-coordinate gradient projection algorithms for submodular maximization
• Approximating graph-constrained max-cut
• Submodular unsplittable flow on trees
• Parametric monotone function maximization with matroid constraints
• Adaptive robust submodular optimization and beyond
• Multi-pass streaming algorithms for monotone submodular function maximization
• Contention resolution, matrix scaling and fair allocation
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Maximum coverage with cluster constraints: an LP-based approximation technique
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Siting renewable power generation assets with combinatorial optimisation
• 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
• A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
• Price of dependence: stochastic submodular maximization with dependent items
• Approximating max-cut under graph-MSO constraints
• Constrained submodular maximization via greedy local search
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• The multi-budget maximum weighted coverage problem
• 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
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Approximation algorithms for stochastic combinatorial optimization problems
• On multiplicative weight updates for concave and submodular function maximization
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Online contention resolution schemes
• The submodular secretary problem goes linear
• Stochastic conditional gradient methods: from convex minimization to submodular maximization
• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• Optimal online contention resolution schemes via ex-ante prophet inequalities
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• 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
• Constrained submodular maximization via a nonsymmetric technique
• Submodular Maximization Through the Lens of Linear Programming
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Understanding the correlation gap for matchings
• Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Online contention resolution schemes with applications to Bayesian selection problems
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Submodular Optimization with Contention Resolution Extensions.
• scientific article; zbMATH DE number 7650099 (Why is no real title available?)
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Fast algorithms for maximizing monotone nonsubmodular functions
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• Approximate multi-matroid intersection via iterative refinement
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Guess free maximization of submodular and linear sums
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• On the correlation gap of matroids
• Towards an optimal contention resolution scheme for matchings
• Distributed strategy selection: a submodular set function maximization approach
• Constrained stochastic submodular maximization with state-dependent costs
• Stochastic Variance Reduction for DR-Submodular Maximization
• DR-submodular function maximization with adaptive stepsize
• Optimal experimental design: formulations and computations
• Maximizing stochastic set function under a matroid constraint from decomposition
• The outer limits of contention resolution on matroids and connections to the secretary problem
• Incremental-decremental maximization
• A prophet inequality based approach to the adaptive ProbeTopK problem
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Pandora's box problem with time constraints
• Simple and optimal online contention resolution schemes for k-uniform matroids
• Correlated stochastic knapsack with a submodular objective
• From contention resolution to matroid secretary and back
• Pairwise independent correlation gap
• Towards an optimal contention resolution scheme for matchings
• On the correlation gap of matroids
• Pairwise-independent contention resolution
• Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity
• Delegated stochastic probing
• Pairwise-independent contention resolution
• Improved approximation factor for adaptive influence maximization via simple greedy strategies
• Random order vertex arrival contention resolution schemes for matching, with applications
• Maximizing the spread of influence through a social network using partial incentives
• A constant approximation algorithm for fair submodular maximization under a knapsack constraint
• Incremental-decremental maximization

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

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