Jaroslaw Byrka

108 papers A* 15A 7B 16Journal 60Unranked 7

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