Optimal approximation for the submodular welfare problem in the value oracle model
From MaRDI portal
Publication:3549686
zbMATH Open1231.91094MaRDI QIDQ3549686FDOQ3549686
Authors: Jan Vondrák 
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 (only showing first 100 items - show all)
- 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
- Multi-agent submodular optimization
- 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
- Mechanism design for perturbation stable combinatorial auctions
- Submodular functions: learnability, structure, and optimization
- Parametric monotone function maximization with matroid constraints
- Black-box reductions in mechanism design
- On maximizing welfare when utility functions are subadditive
- Santa Claus Meets Hypergraph Matchings
- Single-parameter combinatorial auctions with partially public valuations
- Solving packing integer programs via randomized rounding with alterations
- Submodular optimization views on the random assignment problem
- Distributed strategy selection: a submodular set function maximization approach
- Stochastic conditional gradient methods: from convex minimization to submodular maximization
- Non-monotone submodular function maximization under \(k\)-system constraint
- Online submodular welfare maximization: greedy beats 1/2 in random order
- 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
- Maximizing a monotone submodular function subject to a matroid constraint
- Online submodular welfare maximization: greedy is optimal
- Constrained submodular maximization via greedy local search
- On maximizing welfare when utility functions are subadditive
- Online submodular welfare maximization: greedy beats 1/2 in random order
- 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
- Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
- Budget feasible procurement auctions
- 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
- Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
- Truthful randomized mechanisms for combinatorial auctions
- Valuated matroid-based algorithm for submodular welfare problem
- 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
- The submodular welfare problem with demand queries
- Fast algorithms for maximizing monotone nonsubmodular functions
- Title not available (Why is that?)
- Near-optimal asymmetric binary matrix partitions
- Maximizing a class of submodular utility functions
- 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
- The multi-budget maximum weighted coverage problem
- Private non-monotone submodular maximization
- Truthful mechanism design via correlated tree rounding
- 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
- Near-optimal asymmetric binary matrix partitions
- Unified Greedy Approximability beyond Submodular Maximization
- Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
- On a class of covering problems with variable capacities in wireless networks
- Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise
- Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
- Optimal experimental design: formulations and computations
- Title not available (Why is that?)
- Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
- Two-sided capacitated submodular maximization in gig platforms
- Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
- 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
- Profit maximization for multiple products in community-based social networks
- Weak submodularity implies localizability: local search for constrained non-submodular function maximization
- Stochastic Variance Reduction for DR-Submodular Maximization
- Stability and recovery for independence systems
- Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
- Generalized assignment of time-sensitive item groups
- Interactive optimization of submodular functions under matroid constraints
- Optimal bounds on approximation of submodular and XOS functions by juntas
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)
