10 citations · 20 across the 5 of their papers we have counts for
3 papers · 1 filter
New Approximability Results for the Robust k-Median Problem
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn +1
We consider a robust variant of the classical -median problem, introduced by Anthony et al. \cite{AnthonyGGN10}. In the \emph{Robust -Median problem}, we are given an -ver…
Online Checkpointing with Improved Worst-Case Guarantees
Karl Bringmann, Benjamin Doerr, Adrian Neumann +1
In the online checkpointing problem, the task is to continuously maintain a set of k checkpoints that allow to rewind an ongoing computation faster than by a full restart. The only…
Certifying 3-Edge-Connectivity
Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt
We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a…