Image de couverture de livre

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Barak, Zohar, Talgam-Cohen, Inbal
Format:	Preprint
Publié:	2026
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

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

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

An Algorithm-to-Contract Framework without Demand Queries
par: Doron-Arad, Ilan, et autres
Publié: (2025)

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

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

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

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

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

Sum-Of-Squares To Approximate Knapsack
par: Kothari, Pravesh K., et autres
Publié: (2025)

Adaptivity Gaps for Stochastic Probing with Subadditive Functions
par: Li, Jian, et autres
Publié: (2025)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
par: Christalla, Manuel, et autres
Publié: (2025)

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

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

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

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)

An Improved Greedy Approximation for (Metric) $k$-Means
par: Charikar, Moses, et autres
Publié: (2026)

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

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

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)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
par: Kar, Debajyoti, et autres
Publié: (2026)

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

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

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
par: Alipour, Sharareh, et autres
Publié: (2025)

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

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
par: Bienkowski, Marcin, et autres
Publié: (2026)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
par: Hao, Yimin, et autres
Publié: (2025)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
par: Canonne, Clément L., et autres
Publié: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
par: Ma, Will, et autres
Publié: (2019)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
par: Doron-Arad, Ilan, et autres
Publié: (2023)

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
par: Housni, Omar El, et autres
Publié: (2024)

Identifying Approximate Minimizers under Stochastic Uncertainty
par: Al-Thani, Hessa, et autres
Publié: (2025)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
par: Amanatidis, Georgios, et autres
Publié: (2020)

A New Approach for Approximating Directed Rooted Networks
par: Cohen, Sarel, et autres
Publié: (2024)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
par: Bringmann, Karl, et autres
Publié: (2024)

Removable Online Knapsack and Advice
par: Böckenhauer, Hans-Joachim, et autres
Publié: (2020)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
par: Ahmadian, Sara, et autres
Publié: (2024)

Improved Approximations for Flexible Network Design
par: Hyatt-Denesik, Dylan, et autres
Publié: (2024)