3 citations · 5 across the 5 of their papers we have counts for
5 papers · 1 filter
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…
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…