Image de couverture de livre

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Canonne, Clément L., Li, Yun, Umboh, Seeun William
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
par: Dinitz, Michael, et autres
Publié: (2025)

Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
par: Shmoys, David, et autres
Publié: (2026)

Online Computation of String Net Frequency
par: Guo, Peaker, et autres
Publié: (2024)

Online TCP Acknowledgment under General Delays
par: Bhore, Sujoy, et autres
Publié: (2026)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
par: Bartal, Yair, et autres
Publié: (2024)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
par: Cervenjak, Philip, et autres
Publié: (2026)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
par: Cervenjak, Philip, et autres
Publié: (2024)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
par: Ezra, Tomer, et autres
Publié: (2024)

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
par: Canonne, Clément L., et autres
Publié: (2025)

Optimal bounds on a tree inference algorithm
par: Gardiner, Jack, et autres
Publié: (2024)

Colorful Vertex Recoloring of Bipartite Graphs
par: Patt-Shamir, Boaz, et autres
Publié: (2025)

Optimal Dynamic Parameterized Subset Sampling
par: Gan, Junhao, et autres
Publié: (2024)

Locally Private Histograms in All Privacy Regimes
par: Canonne, Clément L., et autres
Publié: (2024)

Uniformity Testing under User-Level Local Privacy
par: Canonne, Clément L., et autres
Publié: (2025)

Simple and Faster Algorithms for Knapsack
par: He, Qizheng, et autres
Publié: (2023)

Instance-Optimal Uniformity Testing and Tracking
par: Blanc, Guy, et autres
Publié: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
par: Jansen, Klaus, et autres
Publié: (2025)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
par: Schlöter, Jens
Publié: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
par: Chen, Lin, et autres
Publié: (2026)

The Discrete Gaussian for Differential Privacy
par: Canonne, Clément L., et autres
Publié: (2020)

Online Unbounded Knapsack
par: Böckenhauer, Hans-Joachim, et autres
Publié: (2024)

Uniformity testing when you have the source code
par: Canonne, Clément L., et autres
Publié: (2024)

Online Knapsack Problems with Estimates
par: Balabán, Jakub, et autres
Publié: (2025)

Average sensitivity of the Knapsack Problem
par: Kumabe, Soh, et autres
Publié: (2024)

Convolution and Knapsack in Higher Dimensions
par: Grage, Kilian, et autres
Publié: (2024)

Fair Submodular Maximization over a Knapsack Constraint
par: Li, Lijun, et autres
Publié: (2025)

Online General Knapsack with Reservation Costs
par: Burjons, Elisabet, et autres
Publié: (2025)

Weakly Approximating Knapsack in Subquadratic Time
par: Chen, Lin, et autres
Publié: (2025)

0-1 Knapsack in Nearly Quadratic Time
par: Jin, Ce
Publié: (2023)

Approximately Counting Knapsack Solutions in Subquadratic Time
par: Feng, Weiming, et autres
Publié: (2024)

A Nearly Quadratic-Time FPTAS for Knapsack
par: Chen, Lin, et autres
Publié: (2023)

Knapsack with Small Items in Near-Quadratic Time
par: Bringmann, Karl
Publié: (2023)

Fine Grained Lower Bounds for Multidimensional Knapsack
par: Doron-Arad, Ilan, et autres
Publié: (2024)

Beyond Worst Case Local Computation Algorithms
par: Biswas, Amartya Shankha, et autres
Publié: (2024)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
par: Dughmi, Shaddin, et autres
Publié: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
par: Mao, Xiao
Publié: (2023)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
par: Barak, Zohar, et autres
Publié: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
par: Azarmehr, Amir, et autres
Publié: (2025)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
par: Gehnen, Matthias, et autres
Publié: (2025)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
par: Buchem, Moritz, et autres
Publié: (2024)