5 papers
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…
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…