28 citations · 126 across the 29 of their papers we have counts for
42 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, Jarosław Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
-Clustering via Iterative Randomized Rounding
Jarosław Byrka, Yuhao Guo, Yang Hu +3
In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for -clustering. As a starting point, we obtain an iterative round…
Servicing Matched Client Pairs with Facilities
Fateme Abbasi, Martin Böhm, Jarosław Byrka +2
We study Facility Location with Matching, a Facility Location problem where, given additional information about which pair of clients is compatible to be matched, we need to match…
Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP
Fateme Abbasi, Hyung-Chan An, Jarosław Byrka +2
Correlation Clustering is a fundamental clustering problem that is generalized to Chromatic Correlation Clustering to incorporate categorical data. Both problems have been intensiv…
Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
Jarosław Byrka, Franciszek Malinka, Tomasz Ponitka
We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS…
Online Rounding Schemes for Edge Cover
Jarosław Byrka, Yongho Shin
Linear programming rounding is a fundamental technique in the design of approximation and online algorithms. A growing body of work has investigated online rounding schemes for var…