3 papers
cs.DS2020
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…
cs.CC2018
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…
cs.DS2018
Short Schedules for Fast Flow Rerouting
Saeed Akhoondian Amiri, Szymon Dudycz, Mahmoud Parham +2
This paper studies the fundamental problem of how to reroute unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new pa…