# Jaroslaw Byrka

According to our database1, Jaroslaw Byrka authored at least 50 papers between 2005 and 2020.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
Online Algorithms for Multilevel Aggregation.
Operations Research, 2020

2019
Dynamic Beats Fixed: On Phase-based Algorithms for File Migration.
ACM Trans. Algorithms, 2019

Concave connection cost Facility Location and the Star Inventory Routing problem.
CoRR, 2019

PTAS for Steiner Tree on Map Graphs.
CoRR, 2019

Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree.
CoRR, 2019

Unbounded lower bound for k-server against weak adversaries.
CoRR, 2019

Better Bounds for Online Line Chasing.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Constant-Factor FPT Approximation for Capacitated k-Median.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Approximation Algorithms for Stochastic and Risk-Averse Optimization.
SIAM J. Discrete Math., 2018

An Improved Approximation Algorithm for Knapsack Median Using Sparsification.
Algorithmica, 2018

Approximating Node-Weighted k-MST on Planar Graphs.
Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Constant-factor approximation for ordered k-median.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Proportional Approval Voting, Harmonic k-median, and Negative Association.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization.
ACM Trans. Algorithms, 2017

2016
Facility Location.
Encyclopedia of Algorithms, 2016

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties).
Theory Comput. Syst., 2016

Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

An Approximation Algorithm for Uniform Capacitated k-Median Problem with 1+\epsilon Capacity Violation.
Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Online Algorithms for Multi-Level Aggregation.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
The interval constrained 3-coloring problem.
Theor. Comput. Sci., 2015

Approximation algorithms for the joint replenishment problem with deadlines.
J. Scheduling, 2015

An approximation algorithm for Uniform Capacitated k-Median problem with 1 + ε capacity violation.
CoRR, 2015

Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Provable fairness for TDMA scheduling.
Proceedings of the 2015 IEEE Conference on Computer Communications, 2015

2014
An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization.
CoRR, 2014

PTAS for Minimax Approval Voting.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Improved Approximation Algorithm for Fault-Tolerant Facility Placement.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Better Approximation Bounds for the Joint Replenishment Problem.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Steiner Tree Approximation via Iterative Randomized Rounding.
J. ACM, 2013

A Constant-Factor Approximation Algorithm for Uniform Hard Capacitated $k$-Median.
CoRR, 2013

Better Approximation Bounds for the Joint Replenishment Problem.
CoRR, 2013

Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter.
Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

Online Control Message Aggregation in Chain Networks.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

2012
Approximation Algorithms for the Joint Replenishment Problem with Deadlines
CoRR, 2012

Drawing (Complete) Binary Tanglegrams - Hardness, Approximation, Fixed-Parameter Tractability.
Algorithmica, 2012

Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Dynamic valuation function based definition of the primary spectrum user in collocated cellular networks.
Proceedings of the 7th International Conference on Cognitive Radio Oriented Wireless Networks, 2012

2010
New algorithms for approximate Nash equilibria in bimatrix games.
Theor. Comput. Sci., 2010

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.
SIAM J. Comput., 2010

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks.
J. Discrete Algorithms, 2010

New results on optimizing rooted triplets consistency.
Discret. Appl. Math., 2010

LP-rounding algorithms for facility-location problems
CoRR, 2010

An improved LP-based approximation for steiner tree.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009
Optimal algorithms for page migration in dynamic networks.
J. Discrete Algorithms, 2009

2008
Facility Location.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Drawing (Complete) Binary Tanglegrams.
Proceedings of the Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, 2008

2007
The approximation gap for the metric facility location problem is not yet closed.
Oper. Res. Lett., 2007

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.
Proceedings of the Approximation, 2007

2005
Bucket Game with Applications to Set Multicover and Dynamic Page Migration.
Proceedings of the Algorithms, 2005