3 papers
cs.DS2026
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_…
cs.DS2026
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…
cs.DS2024
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…