Submodular maximization over multiple matroids via generalized exchange properties

DOI10.1287/MOOR.1100.0463zbMATH Open1216.68342OpenAlexW2113437680MaRDI QIDQ5895002FDOQ5895002

Authors: Jon Lee, Maxim Sviridenko, Jan Vondrák 

Publication date: 27 April 2011

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

Full work available at URL: https://doi.org/10.1287/moor.1100.0463

Recommendations

• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing a monotone submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search

zbMATH Keywords

approximation algorithmmatroidsubmodular function

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Approximation algorithms (68W25) Combinatorial aspects of matroids and geometric lattices (05B35)

Cited In (51)

• Approximation for maximizing monotone non-decreasing set functions with a greedy method
• The matroid intersection cover problem
• Euclidean maximum matchings in the plane -- local to global
• Matroid-constrained vertex cover
• Constrained submodular maximization via a nonsymmetric technique
• Multi-agent submodular optimization
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Title not available (Why is that?)
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint
• Concentration inequalities for nonlinear matroid intersection
• Submodular functions: learnability, structure, and optimization
• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Approximate multi-matroid intersection via iterative refinement
• Submodular stochastic probing on matroids
• Performance bounds with curvature for batched greedy optimization
• Submodular secretary problems: cardinality, matching, and linear constraints
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Approximating graph-constrained max-cut
• Two-sided capacitated submodular maximization in gig platforms
• An improved analysis of local search for max-sum diversification
• Randomized strategies for robust combinatorial optimization with approximate separation
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Improved approximations for \(k\)-exchange systems (extended abstract)
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Submodular Optimization with Contention Resolution Extensions.
• Concentration inequalities for nonlinear matroid intersection
• Generalized budgeted submodular set function maximization
• Generalized budgeted submodular set function maximization
• Max-cut under graph constraints
• The power of subsampling in submodular maximization
• Weak submodularity implies localizability: local search for constrained non-submodular function maximization
• Algorithms as mechanisms: the price of anarchy of relax and round
• Euclidean maximum matchings in the plane -- local to global
• Streaming algorithms for submodular function maximization
• Submodular Maximization Through the Lens of Linear Programming
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• Maximize a monotone function with a generic submodularity ratio
• Multi-pass streaming algorithms for monotone submodular function maximization
• A multi-pass streaming algorithm for regularized submodular maximization
• Analyzing Residual Random Greedy for monotone submodular maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Non-submodular maximization with matroid and knapsack constraints
• Practical budgeted submodular maximization
• The power of local search: maximum coverage over a matroid
• The multi-budget maximum weighted coverage problem
• Approximation algorithm and its performance for maximizing submodular function subject to matroid intersection
• Informative path planning as a maximum traveling salesman problem with submodular rewards
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Submodular maximization over multiple matroids via generalized exchange properties

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