Cover Image

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bienkowski, Marcin, Dallot, Julien, Danelski, Dominik, Pacut, Maciej, Schmid, Stefan
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Minimum Linear Arrangement of Cliques and Lines
by: Dallot, Julien, et al.
Published: (2024)

Online Graph Embedding in Star Graphs
by: Dallot, Julien, et al.
Published: (2026)

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

Dependency-Aware Online Caching
by: Dallot, Julien, et al.
Published: (2024)

Online Algorithms with Unreliable Guidance
by: Dallot, Julien, et al.
Published: (2026)

A Subquadratic Bound for Online Bisection
by: Bienkowski, Marcin, et al.
Published: (2023)

Online Algorithms with Randomly Infused Advice
by: Emek, Yuval, et al.
Published: (2023)

Online Disjoint Set Covers: Randomization is not Necessary
by: Bienkowski, Marcin, et al.
Published: (2024)

Online Bisection with Ring Demands
by: Basiak, Mateusz, et al.
Published: (2026)

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
by: Basiak, Mateusz, et al.
Published: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

Knapsack with Small Items in Near-Quadratic Time
by: Bringmann, Karl
Published: (2023)

Online Unbounded Knapsack
by: Böckenhauer, Hans-Joachim, et al.
Published: (2024)

Online Knapsack Problems with Estimates
by: Balabán, Jakub, et al.
Published: (2025)

Online General Knapsack with Reservation Costs
by: Burjons, Elisabet, et al.
Published: (2025)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
by: Gehnen, Matthias, et al.
Published: (2025)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
by: Räcke, Harald, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Convolution and Knapsack in Higher Dimensions
by: Grage, Kilian, et al.
Published: (2024)

Online Bin Packing with Item Size Estimates
by: Gehnen, Matthias, et al.
Published: (2025)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

Competitive Online Transportation Simplified
by: Arndt, Stephen, et al.
Published: (2025)

Contract Scheduling with Distributional and Multiple Advice
by: Angelopoulos, Spyros, et al.
Published: (2024)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

A Nearly Quadratic-Time FPTAS for Knapsack
by: Chen, Lin, et al.
Published: (2023)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

Competitive Policies for Online Collateral Maintenance
by: Almashaqbeh, Ghada, et al.
Published: (2024)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
by: Barak, Zohar, et al.
Published: (2026)

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

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Fair Submodular Maximization over a Knapsack Constraint
by: Li, Lijun, et al.
Published: (2025)

Time Fairness in Online Knapsack Problems
by: Lechowicz, Adam, et al.
Published: (2023)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
by: Hao, Yimin, et al.
Published: (2025)