Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
From MaRDI portal
Publication:3225171
DOI10.1137/080733991zbMath1234.68459OpenAlexW2132651631MaRDI QIDQ3225171
Gruia Călinescu, Martin Pál, Chandra Chekuri, Jan Vondrák
Publication date: 15 March 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/d611db34db098729a6550d2c5c3fede87c745909
generalized assignment problemapproximation algorithmmatroidsocial welfaremonotone submodular set function
Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (only showing first 100 items - show all)
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ Riemannian optimization via Frank-Wolfe methods ⋮ A bi-criteria algorithm for online non-monotone maximization problems: DR-submodular+concave ⋮ Universal Algorithms for Clustering Problems ⋮ On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms ⋮ On the correlation gap of matroids ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Maximization of nonsubmodular functions under multiple constraints with applications ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Resource time-sharing for IoT applications with deadlines ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ On Fair Division under Heterogeneous Matroid Constraints ⋮ Unified Greedy Approximability beyond Submodular Maximization ⋮ Tight Probability Bounds with Pairwise Independence ⋮ Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ Matroid-constrained vertex cover ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions ⋮ Unified greedy approximability beyond submodular maximization ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems ⋮ Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ 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 ⋮ Unnamed Item ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Sequence submodular maximization meets streaming ⋮ Stochastic submodular probing with state-dependent costs ⋮ Stochastic submodular probing with state-dependent costs ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Online submodular maximization: beating 1/2 made simple ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Guess free maximization of submodular and linear sums ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Stability and Recovery for Independence Systems ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms ⋮ Siting renewable power generation assets with combinatorial optimisation ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Algorithmic Aspects of Private Bayesian Persuasion. ⋮ Maximizing Symmetric Submodular Functions ⋮ Multi-level facility location as the maximization of a submodular set function ⋮ Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex -- ⋮ Two-stage stochastic max-weight independent set problems ⋮ Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ A multi-pass streaming algorithm for regularized submodular maximization ⋮ Measured continuous greedy with differential privacy ⋮ Max-Cut Under Graph Constraints ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Stochastic Probing on Matroids ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Maximizing a monotone non-submodular function under a knapsack constraint ⋮ Fractional 0-1 programming and submodularity ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ The Power of Subsampling in Submodular Maximization ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Online risk-averse submodular maximization ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The multi-budget maximum weighted coverage problem ⋮ Unnamed Item ⋮ Interactive optimization of submodular functions under matroid constraints ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Practical budgeted submodular maximization ⋮ Inequalities on submodular functions via term rewriting ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ Stochastic block-coordinate gradient projection algorithms for submodular maximization ⋮ When Are Welfare Guarantees Robust ⋮ A framework of discrete DC programming by discrete convex analysis ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
This page was built for publication: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
