Unique End of Potential Line

Fearnley, John, Gordon, Spencer, Mehta, Ruta and Savani, Rahul ORCID: 0000-0003-1262-7831 (2019) Unique End of Potential Line .

Text 1811.03841v1.pdf - Submitted version Download (1MB)

Description

The complexity class CLS was proposed by Daskalakis and Papadimitriou in 2011 to understand the complexity of important NP search problems that admit both path following and potential optimizing algorithms. Here we identify a subclass of CLS - called UniqueEOPL - that applies a more specific combinatorial principle that guarantees unique solutions. We show that UniqueEOPL contains several important problems such as the P-matrix Linear Complementarity Problem, finding Fixed Point of Contraction Maps, and solving Unique Sink Orientations (USOs). UniqueEOPL seems to a proper subclass of CLS and looks more likely to be the right class for the problems of interest. We identify a problem - closely related to solving contraction maps and USOs - that is complete for UniqueEOPL. Our results also give the fastest randomised algorithm for P-matrix LCP.

Item Type:	Other
Additional Information:	This paper substantially revises and extends the work described in our previous preprint "End of Potential Line'' (arXiv:1804.03450). The abstract has been shortened to meet the arXiv character limit
Uncontrolled Keywords:	P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search
Depositing User:	Symplectic Admin
Date Deposited:	14 Nov 2018 08:58
Last Modified:	23 May 2026 12:14
DOI:	10.4230/LIPIcs.ICALP.2019.56
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3028777
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.