Optimal approximation for the submodular welfare problem in the value oracle model
From MaRDI portal
Publication:3549686
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)- The Frank-Wolfe algorithm: a short introduction
- Private non-monotone submodular maximization
- Regularized nonmonotone submodular maximization
- Submodular secretary problem with shortlists
- Truthful mechanism design via correlated tree rounding
- 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
- Energy efficient monitoring in sensor networks
- Algorithms for covering multiple submodular constraints and applications
- Natural graph wavelet packet dictionaries
- Improved deterministic algorithms for non-monotone submodular maximization
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- scientific article; zbMATH DE number 7651150 (Why is no real title available?)
- Efficient, optimal stochastic-action selection when limited by an action budget
- Fair allocation of indivisible goods: beyond additive valuations
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
- Near-optimal asymmetric binary matrix partitions
- Greedy is good: constrained non-submodular function maximization via weak submodularity
- A note on solving DiDi's driver-order matching problem
- Unified Greedy Approximability beyond Submodular Maximization
- Multi-agent submodular optimization
- 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
- Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
- Parametric monotone function maximization with matroid constraints
- Mechanism design for perturbation stable combinatorial auctions
- Submodular functions: learnability, structure, and optimization
- 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
- Submodular optimization views on the random assignment problem
- Solving packing integer programs via randomized rounding with alterations
- 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
- Distributed strategy selection: a submodular set function maximization approach
- scientific article; zbMATH DE number 7626767 (Why is no real title available?)
- Stochastic conditional gradient methods: from convex minimization to submodular maximization
- Non-monotone submodular function maximization under \(k\)-system constraint
- Optimal experimental design: formulations and computations
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Economic efficiency requires interaction
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
- Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
- Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
- Two-sided capacitated submodular maximization in gig platforms
- Limitations of randomized mechanisms for combinatorial auctions
- On the Nisan-Ronen conjecture for submodular valuations
- Unified greedy approximability beyond submodular maximization
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
- An accelerated continuous greedy algorithm for maximizing strong submodular functions
- Structured Robust Submodular Maximization: Offline and Online Algorithms
- 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
- Maximizing a monotone submodular function subject to a matroid constraint
- Online submodular welfare maximization: greedy is optimal
- Online submodular welfare maximization: greedy beats 1/2 in random order
- On maximizing welfare when utility functions are subadditive
- Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
- Welfare maximization with production costs: a primal dual approach
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Submodular Optimization with Contention Resolution Extensions.
- Approximation algorithms for the partial assignment problem
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
- Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
- Budget feasible procurement auctions
- Profit maximization for multiple products in community-based social networks
- Robust monotone submodular function maximization
- Stochastic Variance Reduction for DR-Submodular Maximization
- Weak submodularity implies localizability: local search for constrained non-submodular function maximization
- Submodular optimization problems and greedy strategies: a survey
- On Fair Division under Heterogeneous Matroid Constraints
- Submodular functions: from discrete to continuous domains
- Valuated matroid-based algorithm for submodular welfare problem
- A framework of discrete DC programming by discrete convex analysis
- Truthful randomized mechanisms for combinatorial auctions
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- Stability and recovery for independence systems
- Submodular Maximization Through the Lens of Linear Programming
- Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- The submodular welfare problem with demand queries
- scientific article; zbMATH DE number 7559067 (Why is no real title available?)
- Fast algorithms for maximizing monotone nonsubmodular functions
- Interactive optimization of submodular functions under matroid constraints
- Generalized assignment of time-sensitive item groups
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Maximizing a class of submodular utility functions
- Near-optimal asymmetric binary matrix partitions
- Greedy guarantees for non-submodular function maximization under independent system constraint with applications
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)
