3 citations · 5 across the 5 of their papers we have counts for
7 papers
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…
Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
Michaela Borzechowski, John Fearnley, Spencer Gordon +3
We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sin…
On Phases of Unique Sink Orientations
Michaela Borzechowski, Simon Weber
A unique sink orientation (USO) is an orientation of the -dimensional hypercube graph such that every non-empty face contains a unique sink. Schurr showed that given any -dim…
An FPT Algorithm for Splitting a Necklace Among Two Thieves
Michaela Borzechowski, Patrick Schnider, Simon Weber
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness…
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
Michaela Borzechowski, Simon Weber
Klaus showed that the Oriented Matroid Complementarity Problem (OMCP) can be solved by a reduction to the problem of sink-finding in a unique sink orientation (USO) if the input is…
A Universal Construction for Unique Sink Orientations
Michaela Borzechowski, Joseph Doolittle, Simon Weber
Unique Sink Orientations (USOs) of cubes can be used to capture the combinatorial structure of many essential algebraic and geometric problems. For various structural and algorithm…
Unique Sink Orientations of Grids is in Unique End of Potential Line
Michaela Borzechowski, Wolfgang Mulzer
The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. UEOPL captures search problems where the instan…