17 citations · 45 across the 24 of their papers we have counts for
35 papers
Pure Tail Constraints for Online Problems
Mateusz Basiak, Marcin Bienkowski, Yongho Shin +1
Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, w…
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, Jarosław Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
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 Bisection with Ring Demands
Mateusz Basiak, Marcin Bienkowski, Guy Even +1
The online bisection problem requires maintaining a dynamic partition of nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in di…
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm +4
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the ``standard'' model, in which an algorithm is allowed to swap the requ…
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…