Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents

Borzechowski, M, Fearnley, J ORCID: 0000-0003-0791-4342, Gordon, S, Savani, R ORCID: 0000-0003-1262-7831, Schnider, P ORCID: 0000-0002-2172-9285 and Weber, S ORCID: 0000-0003-1901-3621 (2024) Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents .

Access the full-text of this item by clicking on the Open Access link.

Abstract

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 α-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 α-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.

Item Type:	Conference Item (Unspecified)
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	18 Nov 2024 10:34
Last Modified:	13 Jun 2025 19:58
DOI:	10.4230/LIPIcs.ICALP.2024.32
Open Access URL:	https://drops.dagstuhl.de/storage/00lipics/lipics-...
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3188062
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.