Buchumschlag

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ma, Will, Simchi-Levi, David, Zhao, Jinglong
Format:	Preprint
Veröffentlicht:	2019
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Online Knapsack Problems with Estimates
von: Balabán, Jakub, et al.
Veröffentlicht: (2025)

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
von: Bienkowski, Marcin, et al.
Veröffentlicht: (2026)

Online Unbounded Knapsack
von: Böckenhauer, Hans-Joachim, et al.
Veröffentlicht: (2024)

Average sensitivity of the Knapsack Problem
von: Kumabe, Soh, et al.
Veröffentlicht: (2024)

Online General Knapsack with Reservation Costs
von: Burjons, Elisabet, et al.
Veröffentlicht: (2025)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
von: Ganz, Amit, et al.
Veröffentlicht: (2023)

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
von: Goyal, Vineet, et al.
Veröffentlicht: (2020)

Competitive Policies for Online Collateral Maintenance
von: Almashaqbeh, Ghada, et al.
Veröffentlicht: (2024)

Time Fairness in Online Knapsack Problems
von: Lechowicz, Adam, et al.
Veröffentlicht: (2023)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
von: Dughmi, Shaddin, et al.
Veröffentlicht: (2025)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
von: Gehnen, Matthias, et al.
Veröffentlicht: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
von: Chen, Lin, et al.
Veröffentlicht: (2026)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

Removable Online Knapsack and Advice
von: Böckenhauer, Hans-Joachim, et al.
Veröffentlicht: (2020)

Online Edge Coloring: Sharp Thresholds
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

An Exact Solver for Submodular Knapsack Problems
von: Münch, Sabine, et al.
Veröffentlicht: (2025)

Simple and Faster Algorithms for Knapsack
von: He, Qizheng, et al.
Veröffentlicht: (2023)

Convolution and Knapsack in Higher Dimensions
von: Grage, Kilian, et al.
Veröffentlicht: (2024)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2025)

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

Competitive Online Transportation Simplified
von: Arndt, Stephen, et al.
Veröffentlicht: (2025)

The Harmonic Policy for Online Buffer Sharing is (2 + ln n)-Competitive: A Simple Proof
von: Addanki, Vamsi, et al.
Veröffentlicht: (2025)

Generalized Assignment and Knapsack Problems in the Random-Order Model
von: Klimm, Max, et al.
Veröffentlicht: (2025)

Performance of the Extended Ising Machine for the Quadratic Knapsack Problem
von: Akishima, Haruka, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

A Nearly Quadratic-Time FPTAS for Knapsack
von: Chen, Lin, et al.
Veröffentlicht: (2023)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

High-dimensional Linear Bandits with Knapsacks
von: Ma, Wanteng, et al.
Veröffentlicht: (2023)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
von: Schlöter, Jens
Veröffentlicht: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
von: Mao, Xiao
Veröffentlicht: (2023)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
von: Barak, Zohar, et al.
Veröffentlicht: (2026)

Fair Submodular Maximization over a Knapsack Constraint
von: Li, Lijun, et al.
Veröffentlicht: (2025)

Optimizing Inventory Placement for a Downstream Online Matching Problem
von: Epstein, Boris, et al.
Veröffentlicht: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
von: Kar, Debajyoti, et al.
Veröffentlicht: (2026)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
von: Harada, Tsubasa
Veröffentlicht: (2024)

On the FirstFit Algorithm for Online Unit-Interval Coloring
von: Krekelberg, Bob, et al.
Veröffentlicht: (2025)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
von: Hao, Yimin, et al.
Veröffentlicht: (2025)