8 citations · 12 across the 2 of their papers we have counts for
5 papers · 1 filter
An O(loglog n)-Approximation for Submodular Facility Location
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo +4
In the Submodular Facility Location problem (SFL) we are given a collection of clients and facilities in a metric space. A feasible solution consists of an assignment of ea…
Improved Approximation Algorithms for Stochastic-Matching Problems
Marek Adamczyk, Brian Brubach, Fabrizio Grandoni +3
We consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. In this problem, we are given an undirected graph. Each edge i…
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…
Improved Approximation Algorithms for Stochastic Matching
Marek Adamczyk, Fabrizio Grandoni, Joydeep Mukherjee
In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every…