Image de couverture de livre

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Schlöter, Jens
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

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
par: Diwan, Haya, et autres
Publié: (2025)

Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
par: Lindermayr, Alexander, et autres
Publié: (2026)

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

Non-Clairvoyant Scheduling with Progress Bars
par: Benomar, Ziyad, et autres
Publié: (2025)

Online Flow Time Minimization with Gradually Revealed Jobs
par: Lindermayr, Alexander, et autres
Publié: (2026)

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

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

A Little Clairvoyance Is All You Need
par: Gupta, Anupam, et autres
Publié: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
par: Gupta, Anupam, et autres
Publié: (2026)

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
par: Pham, Canh V.
Publié: (2024)

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

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

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

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)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
par: Amanatidis, Georgios, et autres
Publié: (2021)

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)

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

Fair Submodular Maximization over a Knapsack Constraint
par: Li, Lijun, 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)

Hardness and Approximation Algorithms for Balanced Districting Problems
par: Dharangutte, Prathamesh, et autres
Publié: (2025)

New Algorithms and Hardness Results for Connected Clustering
par: Eube, Jan, 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)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
par: Madani, Amirali, et autres
Publié: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
par: Sharma, Eklavya
Publié: (2025)

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

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)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
par: Chen, Shengminjie, et autres
Publié: (2026)

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

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
par: Khanna, Sanjeev, et autres
Publié: (2025)