Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
An effective ergodic theorem and so me applications
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
Develops polynomial-time algorithms achieving competitive ratios of ~1/14.85 (general) and 1/6.86 (unit costs) for submodular welfare maximization with budgets under random-order item arrival.
Introduces constructive Φ-dimension, proves its point-to-set principle and Kolmogorov complexity characterization, and establishes equivalence of faithfulness conditions for Cantor coverings between Hausdorff and constructive levels.
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.
-
Submodular Welfare Maximization with Budget Constraints in the Random-Order Model
Develops polynomial-time algorithms achieving competitive ratios of ~1/14.85 (general) and 1/6.86 (unit costs) for submodular welfare maximization with budgets under random-order item arrival.
-
Point-to-set Principle and Constructive Dimension Faithfulness
Introduces constructive Φ-dimension, proves its point-to-set principle and Kolmogorov complexity characterization, and establishes equivalence of faithfulness conditions for Cantor coverings between Hausdorff and constructive levels.