JB
Jaroslaw Byrka
cs.DScs.DMcs.GTcs.CGcs.LGcs.AIcs.CCmath.OCq-bio.PE
On Valency
published · living versionsW_zjdmufvn·v1 · currentpublished
Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm
with Aravind Srinivasan, Chaitanya Swamy
1 version
Preprints & journals
40 papers in the corpus · 2007–2026Online Rounding Schemes for Edge Cover2507.13159v2 · Jaros\law Byrka, Yongho Shin2025 · 0 citationsarXiv
Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP2510.13446v2 · Fateme Abbasi, Hyung-Chan An, Jaros\law Byrka et al.2025 · 0 citationsarXiv
Incremental Submodular Maximization: Better Than Greedy2606.28558v1 · Marcin Bienkowski, Joakim Blikstad, Jaros\law Byrka et al.2026 · 0 citationsarXiv
Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division2507.14957v2 · Jaros\law Byrka, Franciszek Malinka, Tomasz Ponitka2025 · 1 citationarXiv
Online Disjoint Set Covers: Randomization is not Necessary2404.15554v3 · Marcin Bienkowski, Jaros\law Byrka, \Lukasz Je\.z2024 · 0 citationsarXiv
On the Bidirected Cut Relaxation for Steiner Forest2412.06518v1 · Jaros\law Byrka, Fabrizio Grandoni, Vera Traub2024 · 1 citationarXiv
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces2305.07316v2 · Fateme Abbasi, Sandip Banerjee, Jaros\law Byrka et al.2023 · 1 citation51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 6:1--6:19, Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik, 2024
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 22407.19905v2 · Jaros\law Byrka, Fabrizio Grandoni, Vera Traub2024 · 3 citationsarXiv
Submodularity Gaps for Selected Network Design and Matching Problems2305.10935v1 · Martin Bohm, Jaros\law Byrka, Mateusz Lewandowski et al.2023 · 0 citationsarXiv
Sublogarithmic Approximation for Tollbooth Pricing on a Cactus2305.05405v1 · Andrzej Turko, Jaros\law Byrka2023 · 0 citationsarXiv
Parameterized Approximation Schemes for Clustering with General Norm Objectives2304.03146v1 · Fateme Abbasi, Sandip Banerjee, Jaros\law Byrka et al.2023 · 8 citationsarXiv
An O(loglog n)-Approximation for Submodular Facility Location2211.05474v1 · Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo et al.2022 · 0 citationsarXiv
Online Facility Location with Linear Delay2110.15155v2 · Marcin Bienkowski, Martin Bohm, Jaros\law Byrka et al.2021 · 1 citationarXiv
To Close Is Easier Than To Open: Dual Parameterization To k-Median2011.08083v1 · Jaros\law Byrka, Szymon Dudycz, Pasin Manurangsi et al.2020 · 0 citationsarXiv
Concave connection cost Facility Location and the Star Inventory Routing problem1912.00770v2 · Jaros\law Byrka, Mateusz Lewandowski2019 · 5 citationsarXiv
Unbounded lower bound for k-server against weak adversaries1911.01592v2 · Marcin Bienkowski, Jaros\law Byrka, Christian Coester et al.2019 · 3 citationsarXiv
PTAS for Steiner Tree on Map Graphs1912.00717v1 · Jaros\law Byrka, Mateusz Lewandowski, Syed Mohammad Meesum et al.2019 · 1 citationarXiv
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree1911.02259v2 · Jaros\law Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli2019 · 20 citationsarXiv
Better Bounds for Online Line Chasing1811.09233v2 · Marcin Bienkowski, Jaros\law Byrka, Marek Chrobak et al.2018 · 1 citationarXiv
Dynamic beats fixed: On phase-based algorithms for file migration1609.00831v5 · Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha2016 · 3 citationsarXiv
Constant factor FPT approximation for capacitated k-median1809.05791v1 · Marek Adamczyk, Jaros\law Byrka, Jan Marcinkowski et al.2018 · 16 citationsarXiv
Approximating Node-Weighted k-MST on Planar Graphs1801.00313v2 · Jaros\law Byrka, Mateusz Lewandowski, Joachim Spoerhase2017 · 0 citationsarXiv
Proportional Approval Voting, Harmonic k-median, and Negative Association1704.02183v3 · Jaros\law Byrka, Piotr Skowron, Krzysztof Sornat2017 · 12 citationsarXiv
Constant-Factor Approximation for Ordered k-Median1711.01972v2 · Jaros\law Byrka, Krzysztof Sornat, Joachim Spoerhase2017 · 22 citationsarXiv
Approximation algorithms for stochastic and risk-averse optimization1712.06996v1 · Jaroslaw Byrka, Aravind Srinivasan2017 · 9 citationsarXiv
Bi-Factor Approximation Algorithms for Hard Capacitated $k$-Median Problems1312.6550v3 · Jaros\law Byrka, Krzysztof Fleszar, Bartosz Rybicki et al.2013 · 45 citationsarXiv
Online Algorithms for Multi-Level Aggregation1507.02378v3 · Marcin Bienkowski, Martin Bohm, Jaroslaw Byrka et al.2015 · 9 citationsarXiv
Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter1310.2386v1 · Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki2013 · 4 citationsarXiv
An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization1406.2951v4 · Jaros\law Byrka, Thomas Pensyl, Bartosz Rybicki et al.2014 · 78 citationsProceedings of ACM-Siam Symposium on Discrete Algorithms (SODA), pages 737-756, 2015
Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs1601.02481v1 · Jaros\law Byrka, Mateusz Lewandowski, Carsten Moldenhauer2016 · 3 citationsarXiv
Approximation Algorithms for the Joint Replenishment Problem with Deadlines1212.3233v3 · Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak et al.2012 · 17 citationsJ. Scheduling 18(6): 545-560 (2015)
An approximation algorithm for Uniform Capacitated k-Median problem with 1 + {\epsilon} capacity violation1511.07494v1 · Jaros\law Byrka, Bartosz Rybicki, Sumedha Uniyal2015 · 29 citationsarXiv
Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm1003.1295v1 · Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy2010 · 56 citationsarXivon Valency
Improved approximation algorithm for Fault-Tolerant Facility Placement1311.6615v2 · Bartosz Rybicki, Jaroslaw Byrka2013 · 10 citationsarXiv
Better Approximation Bounds for the Joint Replenishment Problem1307.2531v1 · Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak et al.2013 · 32 citationsarXiv
LP-rounding algorithms for facility-location problems1007.3611v2 · Jaroslaw Byrka, MohammadReza Ghodsi, Aravind Srinivasan2010 · 23 citationsarXiv
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability0806.0920v3 · Kevin Buchin, Maike Buchin, Jaroslaw Byrka et al.2008 · 13 citationsarXiv
The interval constrained 3-coloring problem0907.3563v2 · Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanita2009 · 7 citationsarXiv
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problemcs/0703010v2 · Jaroslaw Byrka, Karen Aardal2007 · 179 citationsarXiv
Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks0710.3258v3 · Jaroslaw Byrka, Pawel Gawrychowski, Katharina T. Huber et al.2007 · 39 citationsarXiv
Career total: 99 works. 40 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.