Fearnley, JS, Gordon, Spencer, Mehta, Ruta and Savani, Rahul ORCID: 0000-0003-1262-7831
(2020)
Unique End of Potential Line.
Journal of Computer and System Sciences, 114.
pp. 1-35.
This is the latest version of this item.
Text
note.pdf - Author Accepted Manuscript Download (546kB) |
|
Text
paper.pdf - Author Accepted Manuscript Download (613kB) | Preview |
Abstract
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 points of Contraction Maps, and solving Unique Sink Orientations (USOs). We identify a problem – closely related to solving contraction maps and USOs – that is complete for UniqueEOPL.
Item Type: | Article |
---|---|
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: | 03 Jun 2020 07:53 |
Last Modified: | 18 Jan 2023 23:50 |
DOI: | 10.1016/j.jcss.2020.05.007 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3089393 |
Available Versions of this Item
-
Unique End of Potential Line. (deposited 29 Apr 2019 08:01)
- Unique End of Potential Line. (deposited 03 Jun 2020 07:53) [Currently Displayed]