Jaroslaw Byrka

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 48

Top Topics

Approximation Algorithms

Facility Location

Top Venues

Publications

Jaroslaw Byrka, Fabrizio Grandoni, Vera Traub
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2. CoRR (2024)
Marcin Bienkowski, Jaroslaw Byrka, Lukasz Jez
Online Disjoint Set Covers: Randomization is not Necessary. CoRR (2024)
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. ICALP (2024)
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jaroslaw Byrka, Fabrizio Grandoni, Krzysztof Sornat, Antoine Tinguely
An O(loglog n)-Approximation for Submodular Facility Location. ICALP (2024)
Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree. SIAM J. Comput. 52 (3) (2023)
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
Parameterized Approximation Schemes for Clustering with General Norm Objectives. CoRR (2023)
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. CoRR (2023)
Martin Böhm, Jaroslaw Byrka, Mateusz Lewandowski, Jan Marcinkowski
Submodularity Gaps for Selected Network Design and Matching Problems. CoRR (2023)
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
Parameterized Approximation Schemes for Clustering with General Norm Objectives. FOCS (2023)
Andrzej Turko, Jaroslaw Byrka
Sublogarithmic Approximation for Tollbooth Pricing on a Cactus. CoRR (2023)
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jaroslaw Byrka, Fabrizio Grandoni, Krzysztof Sornat, Antoine Tinguely
An O(loglog n)-Approximation for Submodular Facility Location. CoRR (2022)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
Online Facility Location with Linear Delay. APPROX/RANDOM (2022)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
New results on multi-level aggregation. Theor. Comput. Sci. 861 (2021)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
Online Facility Location with Linear Delay. CoRR (2021)
Jaroslaw Byrka, Mateusz Lewandowski, Joachim Spoerhase
Approximating Node-Weighted k-MST on Planar Graphs. Theory Comput. Syst. 64 (4) (2020)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
Online Algorithms for Multilevel Aggregation. Oper. Res. 68 (1) (2020)
Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
Unbounded lower bound for k-server against weak adversaries. STOC (2020)
Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michal Wlodarczyk
To Close Is Easier Than To Open: Dual Parameterization To k-Median. CoRR (2020)
Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michal Wlodarczyk
To Close Is Easier Than To Open: Dual Parameterization To k-Median. WAOA (2020)
Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. STOC (2020)
Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal
PTAS for Steiner Tree on Map Graphs. LATIN (2020)
Jaroslaw Byrka, Mateusz Lewandowski
Concave Connection Cost Facility Location and the Star Inventory Routing Problem. WAOA (2020)
Jaroslaw Byrka, Mateusz Lewandowski
Concave connection cost Facility Location and the Star Inventory Routing problem. CoRR (2019)
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
Dynamic Beats Fixed: On Phase-based Algorithms for File Migration. ACM Trans. Algorithms 15 (4) (2019)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
Better Bounds for Online Line Chasing. MFCS (2019)
Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, Michal Wlodarczyk
Constant-Factor FPT Approximation for Capacitated k-Median. ESA (2019)
Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
Unbounded lower bound for k-server against weak adversaries. CoRR (2019)
Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal
PTAS for Steiner Tree on Map Graphs. CoRR (2019)
Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree. CoRR (2019)
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh
An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Algorithmica 80 (4) (2018)
Jaroslaw Byrka, Mateusz Lewandowski, Joachim Spoerhase
Approximating Node-Weighted k-MST on Planar Graphs. CoRR (2018)
Jaroslaw Byrka, Aravind Srinivasan
Approximation Algorithms for Stochastic and Risk-Averse Optimization. SIAM J. Discret. Math. 32 (1) (2018)
Jaroslaw Byrka, Mateusz Lewandowski, Joachim Spoerhase
Approximating Node-Weighted k-MST on Planar Graphs. WAOA (2018)
Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase
Constant-factor approximation for ordered k-median. STOC (2018)
Jaroslaw Byrka, Piotr Skowron, Krzysztof Sornat
Proportional Approval Voting, Harmonic k-median, and Negative Association. ICALP (2018)
Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, Michal Wlodarczyk
Constant factor FPT approximation for capacitated k-median. CoRR (2018)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
Better Bounds for Online Line Chasing. CoRR (2018)
Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase
Constant-Factor Approximation for Ordered k-Median. CoRR (2017)
Jaroslaw Byrka, Piotr Skowron, Krzysztof Sornat
Proportional Approval Voting, Harmonic k-median, and Negative Association. CoRR (2017)
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh
-Median and Positive Correlation in Budgeted Optimization. ACM Trans. Algorithms 13 (2) (2017)
Jaroslaw Byrka, Aravind Srinivasan
Approximation algorithms for stochastic and risk-averse optimization. CoRR (2017)
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration. ICALP (2017)
Jaroslaw Byrka, Bartosz Rybicki, Sumedha Uniyal
An Approximation Algorithm for Uniform Capacitated k-Median Problem with 1+\epsilon Capacity Violation. IPCO (2016)
Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
Dynamic beats fixed: on phase-based algorithms for file migration. CoRR (2016)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Kim Thang Nguyen, Pavel Veselý
Online Algorithms for Multi-Level Aggregation. ESA (2016)
Jaroslaw Byrka, Mateusz Lewandowski, Carsten Moldenhauer
Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs. SWAT (2016)
Jaroslaw Byrka, Mateusz Lewandowski, Carsten Moldenhauer
Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs. CoRR (2016)
Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki
Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties). Theory Comput. Syst. 58 (1) (2016)
Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz R. Kowalski
Provable fairness for TDMA scheduling. INFOCOM (2015)
Jaroslaw Byrka, Bartosz Rybicki, Sumedha Uniyal
An approximation algorithm for Uniform Capacitated k-Median problem with 1 + ε capacity violation. CoRR (2015)
Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase
-Median Problems. SODA (2015)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young
Approximation algorithms for the joint replenishment problem with deadlines. J. Sched. 18 (6) (2015)
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh
-median, and Positive Correlation in Budgeted Optimization. SODA (2015)
Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità
The interval constrained 3-coloring problem. Theor. Comput. Sci. 593 (2015)
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh
An Improved Approximation Algorithm for Knapsack Median Using Sparsification. ESA (2015)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý
Online Algorithms for Multi-Level Aggregation. CoRR (2015)
Bartosz Rybicki, Jaroslaw Byrka
Improved Approximation Algorithm for Fault-Tolerant Facility Placement. WAOA (2014)
Jaroslaw Byrka, Krzysztof Sornat
PTAS for Minimax Approval Voting. CoRR (2014)
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh
An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization. CoRR (2014)
Jaroslaw Byrka, Krzysztof Sornat
PTAS for Minimax Approval Voting. WINE (2014)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall
Better Approximation Bounds for the Joint Replenishment Problem. SODA (2014)
Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase
A Constant-Factor Approximation Algorithm for Uniform Hard Capacitated $k$-Median. CoRR (2013)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young
Approximation Algorithms for the Joint Replenishment Problem with Deadlines. ICALP (1) (2013)
Bartosz Rybicki, Jaroslaw Byrka
Improved approximation algorithm for Fault-Tolerant Facility Placement. CoRR (2013)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall
Better Approximation Bounds for the Joint Replenishment Problem. CoRR (2013)
Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki
Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter. WAOA (2013)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall, Grzegorz Stachowiak
Online Control Message Aggregation in Chain Networks. WADS (2013)
Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki
Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter. CoRR (2013)
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità
Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM 60 (1) (2013)
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, Alexander Wolff
Drawing (Complete) Binary Tanglegrams - Hardness, Approximation, Fixed-Parameter Tractability. Algorithmica 62 (1-2) (2012)
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak
Approximation Algorithms for the Joint Replenishment Problem with Deadlines CoRR (2012)
Michal Szydelko, Jaroslaw Byrka, Jakub Oszmianski
Dynamic valuation function based definition of the primary spectrum user in collocated cellular networks. CrownCom (2012)
Jaroslaw Byrka, Bartosz Rybicki
Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location. ICALP (1) (2012)
Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy
Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm CoRR (2010)
Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità
The Interval Constrained 3-Coloring Problem. LATIN (2010)
Jaroslaw Byrka, Karen Aardal
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. SIAM J. Comput. 39 (6) (2010)
Jaroslaw Byrka, Pawel Gawrychowski, Katharina T. Huber, Steven Kelk
Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. J. Discrete Algorithms 8 (1) (2010)
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità
An improved LP-based approximation for steiner tree. STOC (2010)
Jaroslaw Byrka, Mohammadreza Ghodsi, Aravind Srinivasan
LP-rounding algorithms for facility-location problems CoRR (2010)
Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson
New results on optimizing rooted triplets consistency. Discret. Appl. Math. 158 (11) (2010)
Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy
Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm. IPCO (2010)
Hartwig Bosse, Jaroslaw Byrka, Evangelos Markakis
New algorithms for approximate Nash equilibria in bimatrix games. Theor. Comput. Sci. 411 (1) (2010)
Marcin Bienkowski, Jaroslaw Byrka, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide
Optimal algorithms for page migration in dynamic networks. J. Discrete Algorithms 7 (4) (2009)
Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità
The interval constrained 3-coloring problem CoRR (2009)
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, Alexander Wolff
Drawing (Complete) Binary Tanglegrams. Graph Drawing (2008)
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, Alexander Wolff
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability CoRR (2008)
Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson
New Results on Optimizing Rooted Triplets Consistency. ISAAC (2008)
Hartwig Bosse, Jaroslaw Byrka, Evangelos Markakis
New Algorithms for Approximate Nash Equilibria in Bimatrix Games. WINE (2007)
Jaroslaw Byrka, Karen Aardal
The approximation gap for the metric facility location problem is not yet closed. Oper. Res. Lett. 35 (3) (2007)
Jaroslaw Byrka
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem CoRR (2007)
Jaroslaw Byrka
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. APPROX-RANDOM (2007)
Marcin Bienkowski, Jaroslaw Byrka
Bucket Game with Applications to Set Multicover and Dynamic Page Migration. ESA (2005)