6 papers
Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
Marcin Bienkowski, Julien Dallot, Dominik Danelski +2
Payment channel networks (PCNs) are a promising approach to making cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing transa…
Online Graph Embedding in Star Graphs
Julien Dallot, Darya Melnyk, Maciej Pacut +1
Graph embedding is a fundamental problem of mapping nodes of a guest graph into a host graph while minimizing the distance distortion, with broad applications, including virtual ne…
Online Algorithms with Unreliable Guidance
Julien Dallot, Yuval Emek, Yuval Gil +2
This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic compon…
Online Algorithms with Randomly Infused Advice
Yuval Emek, Yuval Gil, Maciej Pacut +1
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In cont…
The Harmonic Policy for Online Buffer Sharing is (2 + ln n)-Competitive: A Simple Proof
Vamsi Addanki, Julien Dallot, Leon Kellerhals +2
The problem of online buffer sharing is expressed as follows. A switch with output ports receives a stream of incoming packets. When an incoming packet is accepted by the switc…
RIFO: Pushing the Efficiency of Programmable Packet Schedulers
Habib Mostafaei, Maciej Pacut, Stefan Schmid
Packet scheduling is a fundamental networking task that recently received renewed attention in the context of programmable data planes. Programmable packet scheduling systems such…