4 citations · 4 across the 4 of their papers we have counts for
5 papers · 1 filter
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…
Connected Components at Scale via Local Contractions
Jakub Łącki, Vahab Mirrokni, Michał Włodarczyk
As a fundamental tool in hierarchical graph clustering, computing connected components has been a central problem in large-scale data mining. While many known algorithms have been…
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…
A Subquadratic Approximation Scheme for Partition
Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk
The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an $\widetilde{O}(n+1/\vareps…
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li +2
We study the problem of deleting the smallest set of vertices (resp. edges) from a given graph such that the induced subgraph (resp. subgraph) belongs to so…