Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

DOI10.1007/978-3-540-72792-7_15zbMath1136.90449OpenAlexW2129866531MaRDI QIDQ5429267

Jan Vondrák, Martin Pál, Gruia Călinescu, Chandra Chekuri

Publication date: 29 November 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72792-7_15

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (50)

Submodularity and Randomized rounding techniques for Optimal Experimental Design ⋮ Provable randomized rounding for minimum-similarity diversification ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Experimental Design for Nonparametric Correction of Misspecified Dynamical Models ⋮ A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Robust Adaptive Submodular Maximization ⋮ Idempotent Expansions for Continuous-Time Stochastic Control ⋮ Submodular Stochastic Probing on Matroids ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ New dominating sets in social networks ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Matroid rank functions and discrete concavity ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Submodular spectral functions of principal submatrices of a Hermitian matrix, extensions and applications ⋮ Beyond submodularity: a unified framework of randomized set selection with group fairness constraints ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ On the correlation gap of matroids ⋮ Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ Matroid-constrained vertex cover ⋮ Streaming submodular maximization with the chance constraint ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ Randomized strategies for robust combinatorial optimization with approximate separation ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Sell or hold: A simple two-stage stochastic combinatorial optimization problem ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ Recent Developments in Discrete Convex Analysis ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Robust mechanisms for risk-averse sellers ⋮ Maximize a monotone function with a generic submodularity ratio ⋮ Submodular Optimization with Contention Resolution Extensions. ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Contact Center Scheduling with Strict Resource Requirements ⋮ Submodular Cost Allocation Problem and Applications ⋮ Parametric monotone function maximization with matroid constraints ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Unnamed Item ⋮ Game-theoretic derivation of upper hedging prices of multivariate contingent claims and submodularity ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ Tight approximation bounds for maximum multi-coverage

This page was built for publication: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)