Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
<|reference_start|>Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents: 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 sink orientation (USO), and a variant of the $\alpha$-Ham Sandwich problem. For all three settings, we show that "two choices are enough", meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our $\alpha$-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs.<|reference_end|>
@article{borzechowski2024two,
    title={Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents},
    author={Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani,
  Patrick Schnider, Simon Weber},
    journal={arXiv preprint arXiv:2402.07683},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07683},
    primaryClass={cs.CC cs.CG math.OC}
}