4 papers · 1 filter
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
Franziska Eberle, Ruben Hoeksma, Nicole Megow +3
The speed-robust scheduling problem is a two-stage problem where given machines, jobs must be grouped into at most bags while the processing speeds of the given machine…
On Minimum Generalized Manhattan Connections
Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook +5
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points in the plane, together with a subset of pairs of points in (wh…
On Hop-Constrained Steiner Trees in Tree-Like Metrics
Martin Böhm, Ruben Hoeksma, Nicole Megow +2
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint which requires the depth of the tree to be at most . Our main result is an exact algor…
Online Minimum Cost Matching on the Line with Recourse
Nicole Megow, Lukas Nölke
In online minimum cost matching on the line, requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The…