CaltechAUTHORS
  A Caltech Library Service

Unique end of potential line

Fearnley, John and Gordon, Spencer and Mehta, Ruta and Savani, Rahul (2020) Unique end of potential line. Journal of Computer and System Sciences, 114 . pp. 1-35. ISSN 0022-0000. https://resolver.caltech.edu/CaltechAUTHORS:20200602-071452499

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200602-071452499

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
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.jcss.2020.05.007DOIArticle
ORCID:
AuthorORCID
Savani, Rahul0000-0003-1262-7831
Additional Information:© 2020 Elsevier Inc. Received 18 June 2019, Revised 19 March 2020, Accepted 20 May 2020, Available online 1 June 2020.
Record Number:CaltechAUTHORS:20200602-071452499
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200602-071452499
Official Citation:John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani, Unique end of potential line, Journal of Computer and System Sciences, Volume 114, 2020, Pages 1-35, ISSN 0022-0000, https://doi.org/10.1016/j.jcss.2020.05.007. (http://www.sciencedirect.com/science/article/pii/S0022000020300520)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103628
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:02 Jun 2020 16:08
Last Modified:08 Jun 2020 19:36

Repository Staff Only: item control page