Cover Image

The Harmonic Policy for Online Buffer Sharing is (2 + ln n)-Competitive: A Simple Proof

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Addanki, Vamsi, Dallot, Julien, Kellerhals, Leon, Pacut, Maciej, Schmid, Stefan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
by: Bienkowski, Marcin, et al.
Published: (2026)

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

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

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

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

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

Designing Approximate Binary Trees for Trees
by: Kellerhals, Leon, et al.
Published: (2026)

Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions
by: Addanki, Vamsi, et al.
Published: (2024)

Locally Rainbow Paths
by: Fluschnik, Till, et al.
Published: (2024)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

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

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

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
by: Wallisch, Christian, et al.
Published: (2025)

Modification-Fair Cluster Editing
by: Froese, Vincent, et al.
Published: (2021)

Placing Green Bridges Optimally, with a Multivariate Analysis
by: Fluschnik, Till, et al.
Published: (2021)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Vermilion: A Traffic-Aware Reconfigurable Optical Interconnect with Formal Throughput Guarantees
by: Addanki, Vamsi, et al.
Published: (2025)

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

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

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

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

Buffered Streaming Edge Partitioning
by: Chhabra, Adil, et al.
Published: (2024)

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
by: Goyal, Vineet, et al.
Published: (2020)

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

Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms
by: Xu, Pan
Published: (2024)

A Simple Proof that Ricochet Robots is PSPACE-Complete
by: Balanza-Martinez, Jose, et al.
Published: (2024)

The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
by: Haas, Niklas, et al.
Published: (2025)

Online Matching under KIID: Enhanced Competitive Analysis through Ordinary Differential Equation Systems
by: Xu, Pan
Published: (2025)

Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies
by: Alif, Lamya, et al.
Published: (2026)

Hash & Adjust: Competitive Demand-Aware Consistent Hashing
by: Pourdamghani, Arash, et al.
Published: (2024)

Online Allocation with Unknown Shared Supply
by: Neoh, Tzeh Yuan, et al.
Published: (2026)

Complexity of Perfect and Ideal Resilience Verification in Fast Re-Route Networks
by: Bentert, Matthias, et al.
Published: (2026)

Competitively Consistent Clustering
by: Buchbinder, Niv, et al.
Published: (2025)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
by: Pabbaraju, Chirag, et al.
Published: (2025)

Simple Grid Polygon Online Exploration Revisited
by: Brock, Maximilian, et al.
Published: (2024)

Tree Proof-of-Position Algorithms
by: Kharman, Aida Manzano, et al.
Published: (2024)

A Competitive Algorithm for Throughput Maximization on Identical Machines
by: Moseley, Benjamin, et al.
Published: (2021)