4 citations · 8 across the 14 of their papers we have counts for
17 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…
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…
Learning Minimum Linear Arrangement of Cliques and Lines
Julien Dallot, Maciej Pacut, Marcin Bienkowski +2
In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is m…
Dependency-Aware Online Caching
Julien Dallot, Amirmehdi Jafari Fesharaki, Maciej Pacut +1
We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also…
Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions
Vamsi Addanki, Maciej Pacut, Stefan Schmid
Packet buffers in datacenter switches are shared across all the switch ports in order to improve the overall throughput. The trend of shrinking buffer sizes in datacenter switches…
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…
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…
Self-Adjusting Packet Classification
Maciej Pacut, Juan Vanerio, Vamsi Addanki +3
This paper is motivated by the vision of more efficient packet classification mechanisms that self-optimize in a demand-aware manner. At the heart of our approach lies a self-adjus…
Online List Access with Precedence Constraints
Maciej Pacut, Juan Vanerio, Vamsi Addanki +3
This paper considers a natural generalization of the online list access problem in the paid exchange model, where additionally there can be precedence constraints ("dependencies")…
Temporal Locality in Online Algorithms
Maciej Pacut, Mahmoud Parham, Joel Rybicki +3
Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the…
An Optimal Algorithm for Online Multiple Knapsack
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of bins (knapsacks) of equal…
Online Tree Caching
Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut +3
We initiate the study of a natural and practically relevant new variant of online caching where the to-be-cached items can have dependencies. We assume that the universe is a tree…
Dynamic Balanced Graph Partitioning
Chen Avin, Marcin Bienkowski, Andreas Loukas +2
This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between…
Hardness of Virtual Network Embedding with Replica Selection
Carlo Fuerst, Maciej Pacut, Stefan Schmid
Efficient embedding virtual clusters in physical network is a challenging problem. In this paper we consider a scenario where physical network has a structure of a balanced tree. T…
Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem
Michał Karpiński, Maciej Pacut
The goal of this paper is to propose and test a new memetic algorithm for the capacitated vehicle routing problem in parallel computing environment. In this paper we consider simpl…