Research map / Learning theory and algorithms / Sample complexity
The Adaptive Complexity of Maximizing a Gross Substitutes Valuation
Ron Kupfer, Sharon Qian, Eric Balkanski, Yaron Singer
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GSAS (adaptive sequencing with low initial threshold) instead of Trimmed Greedy under the same round budget | GSAS · Synthetic OXS graphs G1-G4 | normalized valuation | Improved |
| Use GSAS instead of Adaptive Sampling | GSAS · Twitter graph (Figure 2) | normalized valuation | Improved |
| Learn the OXS valuation by sampling then run greedy (Learned Opt) instead of querying the true function | Learned Opt baseline · Synthetic OXS graphs G1-G4 | normalized valuation | Hurt |
| Increase cardinality k from small values to larger values (k above 80) | GSAS · Twitter graphs G5-G8 | number of rounds relative to Greedy | Improved |
| Compare GSAS with Greedy at small k (below 80) | GSAS · Twitter graphs G5-G8 | normalized valuation | No clear effect |
| Lower the initial threshold to OPT/(eps k) instead of max f(a) | GSAS · Theory (adaptivity) | adaptive rounds | Improved |
| Use Top-k instead of GSAS when valuation is purely additive or purely unit-demand | Top-k baseline · UD-additivity spectrum (n=1024, k=32) | normalized valuation | No clear effect |
| Use GSAS on valuations between unit-demand and additive instead of baselines | GSAS · UD-additivity spectrum, m from 1 to 1024 | normalized valuation | Improved |
| Allow queries of non-feasible sets (stronger model) for non-adaptive algorithms | Non-adaptive algorithms (lower bound) · Theory | approximation ratio: 1/2 + eps | Hurt |
Closest papers by meaning
- Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity (ICML 2021 · similarity 0.88)
- Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice (ICML 2018 · similarity 0.88)
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.87)
- A Unified Approach to Submodular Maximization Under Noise (NeurIPS 2025 · similarity 0.86)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.86)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
