Sebastian Haslebacher

collaborators

6 papers

cs.DS2026

Faster Approximate Fixed Points of $ℓ_{\infty}$ -Contractions

Andrei Feodorov, Sebastian Haslebacher

We present a new algorithm for finding an $I^µ$ -approximate fixed point of an $ℓ_{\infty}$ -contracting function $f : [0, 1]^{d} \to [0, 1]^{d}$ . Our algorithm is based on the q…

math.CO2026

Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements

Michaela Borzechowski, Sebastian Haslebacher, Hung P. Hoang +2

The famous Ham-Sandwich theorem states that any $d$ point sets in $R^{d}$ can be simultaneously bisected by a single hyperplane. The $I^\pm$ -Ham-Sandwich theorem gives a suffic…

cs.DS2025

A Levelset Algorithm for 3D-Tarski

Sebastian Haslebacher, Jonas Lill

We present a simple new algorithm for finding a Tarski fixed point of a monotone function $F : [N]^{3} \to [N]^{3}$ . Our algorithm runs in $O (lo g^{2} N)$ time and makes $O(\log^…

cs.DS2025

On Finding $ℓ$ -th Smallest Perfect Matchings

Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1

Given an undirected weighted graph $G$ and an integer $k$ , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly $k$ in $G$ . In this p…

cs.DS2025

ARRIVAL: Recursive Framework & $ℓ_{1}$ -Contraction

Sebastian Haslebacher

ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, accordi…

cs.CC2025

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions

Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1

We prove that an $I^µ$ -approximate fixpoint of a map $f : [0, 1]^{d} \to [0, 1]^{d}$ can be found with $O (d^{2} (lo g \frac{1}{I ^} µ + lo g \frac{1}{1 - I ^ »}))$ queries to $f$ if $f$ i…

Faster Approximate Fixed Points of ℓ∞​-Contractions

Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements

A Levelset Algorithm for 3D-Tarski

On Finding ℓ-th Smallest Perfect Matchings

ARRIVAL: Recursive Framework & ℓ1​-Contraction

Query-Efficient Fixpoints of ℓp​-Contractions

Faster Approximate Fixed Points of $ℓ_{\infty}$ -Contractions

On Finding $ℓ$ -th Smallest Perfect Matchings

ARRIVAL: Recursive Framework & $ℓ_{1}$ -Contraction

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions