Lukas Retschmeier

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

Revisiting a Successful Reduction Rule for Dominating Set

Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3

Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D \subseteq V$ of minimal cardinality such that every vertex either is in $D$ …

cs.DS2024

The Correlated Gaussian Sparse Histogram Mechanism

Christian Janos Lebeda, Lukas Retschmeier

We consider the problem of releasing a sparse histogram under $(ε, δ)$ -differential privacy. The stability histogram independently adds noise from a Laplace or Gaussian d…

cs.DS2024

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

Rasmus Pagh, Lukas Retschmeier, Hao Wu +1

We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph $G = (V, E, W)$ where $V$ is a set of $n$ vertices, $E$ is a set of $m$ …