2 citations · 4 across the 7 of their papers we have counts for
18 papers
Servicing Matched Client Pairs with Facilities
Fateme Abbasi, Martin Böhm, Jarosław Byrka +2
We study Facility Location with Matching, a Facility Location problem where, given additional information about which pair of clients is compatible to be matched, we need to match…
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm +4
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the ``standard'' model, in which an algorithm is allowed to swap the requ…
Improved online load balancing with known makespan
Martin Böhm, Matej Lieskovský, Sören Schmitt +2
We break the barrier of for the problem of online load balancing with known makespan, also known as bin stretching. In this problem, identical machines and the optimal ma…
Approximating Traveling Salesman Problems Using a Bridge Lemma
Martin Böhm, Zachary Friggstad, Tobias Mömke +1
We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_…
Submodularity Gaps for Selected Network Design and Matching Problems
Martin Böhm, Jarosław Byrka, Mateusz Lewandowski +1
Submodularity in combinatorial optimization has been a topic of many studies and various algorithmic techniques exploiting submodularity of a studied problem have been proposed. It…
Online Facility Location with Linear Delay
Marcin Bienkowski, Martin Böhm, Jarosław Byrka +1
We study the problem of online facility location with delay. In this problem, a sequence of clients appear in the metric space, and they need to be eventually connected to some…