4 citations · 4 across the 4 of their papers we have counts for
10 papers
Submodularity Gaps for Selected Network Design and Matching Problems
Martin Böhm, Jarosław Byrka, Mateusz Lewandowski +1
Submodularity in combinatorial optimization has been a topic of many studies and various algorithmic techniques exploiting submodularity of a studied problem have been proposed. It…
Online Facility Location with Linear Delay
Marcin Bienkowski, Martin Böhm, Jarosław Byrka +1
We study the problem of online facility location with delay. In this problem, a sequence of clients appear in the metric space, and they need to be eventually connected to some…
To Close Is Easier Than To Open: Dual Parameterization To k-Median
Jarosław Byrka, Szymon Dudycz, Pasin Manurangsi +2
The -Median problem is one of the well-known optimization problems that formalize the task of data clustering. Here, we are given sets of facilities and clients , and the…
Online Dynamic B-Matching With Applications to Reconfigurable Datacenter Networks
Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski +1
This paper initiates the study of online algorithms for the maximum weight -matching problem, a generalization of maximum weight matching where each node has at most …
Tight Approximation Ratio for Minimum Maximal Matching
Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
We study a combinatorial problem called Minimum Maximal Matching, where we are asked to find in a general graph the smallest that can not be extended. We show that this problem is…
Constant factor FPT approximation for capacitated k-median
Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski +2
Capacitated k-median is one of the few outstanding optimization problems for which the existence of a polynomial time constant factor approximation algorithm remains an open proble…
Logarithmic price of buffer downscaling on line metrics
Marcin Bienkowski, Martin Böhm, Łukasz Jeż +5
We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant delta, an (offline) algorithm that has a buffer (1-delta) k p…
Transiently Consistent SDN Updates: Being Greedy is Hard
Saeed Akhoondian Amiri, Arne Ludwig, Jan Marcinkowski +1
The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logical…
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…
A - Approximation Algorithm for the Maximum Traveling Salesman Problem
Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch +1
In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour…