4 citations · 4 across the 4 of their papers we have counts for
8 papers · 1 filter
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
Bart M. P. Jansen, Michał Włodarczyk
In the F-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family F. The Vertex planarization pr…
Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size
Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk
In the -Minor-Free Deletion problem one is given an undirected graph , an integer , and the task is to determine whether there exists a vertex set of size at…
On the Hardness of Compressing Weights
Bart M. P. Jansen, Shivesh K. Roy, Michał Włodarczyk
We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the inst…
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…
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…
Random Order Contention Resolution Schemes
Marek Adamczyk, Michał Włodarczyk
Contention resolution schemes have proven to be an incredibly powerful concept which allows to tackle a broad class of problems. The framework has been initially designed to handle…