Unique End of Potential Line



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. 1 - 35.

This is the latest version of this item.

[img] Text
note.pdf - Accepted Version

Download (546kB)
[img] Text
paper.pdf - Accepted Version

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: 17 Aug 2022 16:11
DOI: 10.1016/j.jcss.2020.05.007
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3089393

Available Versions of this Item