Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
Title resolution pending
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
years
2026 4verdicts
UNVERDICTED 4representative citing papers
Learning-augmented mechanism using identity-of-max predictions for online utility maximization achieves consistency to full-info optimum and robustness to best implementable solution.
A uniform sample of size O(ε^{-2} log 1/ε) is a stable (ε, O(ε))-coreset for the geometric median with high probability, tight up to the log factor.
Designs optimal and approximately optimal mechanisms for buyer utility and welfare objectives in budget-feasible procurement, including prior-free constant-factor approximations for welfare and Bayesian near-optimal mechanisms for utility.
citing papers explorer
-
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
-
Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization
Learning-augmented mechanism using identity-of-max predictions for online utility maximization achieves consistency to full-info optimum and robustness to best implementable solution.
-
Optimal Stable Coresets for Geometric Median via Uniform Sampling
A uniform sample of size O(ε^{-2} log 1/ε) is a stable (ε, O(ε))-coreset for the geometric median with high probability, tight up to the log factor.
-
From Welfare to Utility: Generalized Objectives in Budget-Feasible Procurement
Designs optimal and approximately optimal mechanisms for buyer utility and welfare objectives in budget-feasible procurement, including prior-free constant-factor approximations for welfare and Bayesian near-optimal mechanisms for utility.