Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.
26 Joseph Y-T Leung and Chung-Lun Li
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.
Develops a learning-augmented polynomial-time algorithm for R||C_max that achieves (1+ε)-approximation under accurate predictions of heavy job assignments and falls back to 2-approximation otherwise.
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
citing papers explorer
-
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.
-
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Develops a learning-augmented polynomial-time algorithm for R||C_max that achieves (1+ε)-approximation under accurate predictions of heavy job assignments and falls back to 2-approximation otherwise.
-
Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.