Optimal approximation for the submodular welfare problem in the value oracle model
From MaRDI portal
Publication:3549686
zbMATH Open1231.91094MaRDI QIDQ3549686FDOQ3549686
Publication date: 5 January 2009
Recommendations
- Maximizing a monotone submodular function subject to a matroid constraint
- The submodular welfare problem with demand queries
- Online submodular welfare maximization: greedy is optimal
- Fast algorithms for maximizing submodular functions
- Online submodular welfare maximization: greedy beats 1/2 in random order
Cited In (98)
- Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization
- Improved deterministic algorithms for non-monotone submodular maximization
- Efficient, optimal stochastic-action selection when limited by an action budget
- Greedy is good: constrained non-submodular function maximization via weak submodularity
- Unified Greedy Approximability beyond Submodular Maximization
- Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
- Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise
- Optimal experimental design: formulations and computations
- Title not available (Why is that?)
- Stability and Recovery for Independence Systems
- Near-Optimal Asymmetric Binary Matrix Partitions
- Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
- Two-sided capacitated submodular maximization in gig platforms
- Title not available (Why is that?)
- On the Nisan-Ronen conjecture for submodular valuations
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
- Title not available (Why is that?)
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Submodular Optimization with Contention Resolution Extensions.
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
- Weak submodularity implies localizability: local search for constrained non-submodular function maximization
- Stochastic Variance Reduction for DR-Submodular Maximization
- Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
- Interactive optimization of submodular functions under matroid constraints
- Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
- Greedy guarantees for non-submodular function maximization under independent system constraint with applications
- Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions
- Title not available (Why is that?)
- The Frank-Wolfe algorithm: a short introduction
- Regularized nonmonotone submodular maximization
- Improved deterministic algorithms for non-monotone submodular maximization
- Optimization with demand oracles
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- Algorithms for covering multiple submodular constraints and applications
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- Energy efficient monitoring in sensor networks
- Title not available (Why is that?)
- Natural graph wavelet packet dictionaries
- Fair allocation of indivisible goods: beyond additive valuations
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- A note on solving DiDi's driver-order matching problem
- Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- On a class of covering problems with variable capacities in wireless networks
- Mechanism design for perturbation stable combinatorial auctions
- Parametric monotone function maximization with matroid constraints
- Budget Feasible Procurement Auctions
- Santa Claus Meets Hypergraph Matchings
- Title not available (Why is that?)
- Distributed strategy selection: a submodular set function maximization approach
- Non-monotone submodular function maximization under \(k\)-system constraint
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- Economic efficiency requires interaction
- Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
- Unified greedy approximability beyond submodular maximization
- Limitations of randomized mechanisms for combinatorial auctions
- Structured Robust Submodular Maximization: Offline and Online Algorithms
- An accelerated continuous greedy algorithm for maximizing strong submodular functions
- Measured continuous greedy with differential privacy
- Policies for risk-aware sensor data collection by mobile agents
- Non-submodular streaming maximization with minimum memory and low adaptive complexity
- Constrained submodular maximization via greedy local search
- Black-Box Reductions in Mechanism Design
- Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Welfare maximization with production costs: a primal dual approach
- Approximation algorithms for the partial assignment problem
- Single-Parameter Combinatorial Auctions with Partially Public Valuations
- Profit maximization for multiple products in community-based social networks
- Robust monotone submodular function maximization
- Title not available (Why is that?)
- On Fair Division under Heterogeneous Matroid Constraints
- Submodular optimization problems and greedy strategies: a survey
- Submodular functions: from discrete to continuous domains
- Submodular Functions: Learnability, Structure, and Optimization
- Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
- Truthful randomized mechanisms for combinatorial auctions
- Title not available (Why is that?)
- A framework of discrete DC programming by discrete convex analysis
- Submodular Maximization Through the Lens of Linear Programming
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- Fast algorithms for maximizing monotone nonsubmodular functions
- Title not available (Why is that?)
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Near-optimal asymmetric binary matrix partitions
- Maximizing a class of submodular utility functions
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
- Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- Title not available (Why is that?)
- Title not available (Why is that?)
- The multi-budget maximum weighted coverage problem
- Private non-monotone submodular maximization
- Truthful mechanism design via correlated tree rounding
This page was built for publication: Optimal approximation for the submodular welfare problem in the value oracle model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549686)
