3 citations · 4 across the 8 of their papers we have counts for
8 papers
Faster Approximate Fixed Points of -Contractions
Andrei Feodorov, Sebastian Haslebacher
We present a new algorithm for finding an -approximate fixed point of an -contracting function . Our algorithm is based on the qu…
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 point sets in can be simultaneously bisected by a single hyperplane. The -Ham-Sandwich theorem gives a suffici…
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 . Our algorithm runs in time and makes $O(\log^…
On Finding -th Smallest Perfect Matchings
Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1
Given an undirected weighted graph and an integer , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly in . In this p…
Query-Efficient Fixpoints of -Contractions
Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1
We prove that an -approximate fixpoint of a map can be found with queries to if is $…
ARRIVAL: Recursive Framework & -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…
On the Exact Matching Problem in Dense Graphs
Nicolas El Maalouly, Sebastian Haslebacher, Lasse Wulf
In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly…
A Subexponential Algorithm for ARRIVAL
Bernd Gärtner, Sebastian Haslebacher, Hung P. Hoang
The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in $NP \cap…