5 papers
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…
Online Disjoint Set Covers: Randomization is not Necessary
Marcin Bienkowski, JarosÅaw Byrka, Åukasz Jeż
In the online disjoint set covers problem, the edges of a hypergraph are revealed online, and the goal is to partition them into a maximum number of disjoint set covers. That is, n…