28 citations · 31 across the 5 of their papers we have counts for
6 papers
A - Approximation Algorithm for the Maximum Traveling Salesman Problem
Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch +1
In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour…
An approximation algorithm for Uniform Capacitated k-Median problem with 1 + ε capacity violation
Jarosław Byrka, Bartosz Rybicki, Sumedha Uniyal
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the sta…
An Improved Approximation for -median, and Positive Correlation in Budgeted Optimization
Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki +2
Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However,…
Bi-Factor Approximation Algorithms for Hard Capacitated -Median Problems
Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki +1
The -Facility Location problem is a generalization of the classical problems -Median and Facility Location. The goal is to select a subset of at most facilities that mini…
Improved approximation algorithm for Fault-Tolerant Facility Placement
Bartosz Rybicki, Jaroslaw Byrka
We consider the Fault-Tolerant Facility Placement problem (), which is a generalization of the classical Uncapacitated Facility Location problem (). In the proble…
Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter
Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki
The state of the art in approximation algorithms for facility location problems are complicated combinations of various techniques. In particular, the currently best 1.488-approxim…