Unique end of potential line

John Fearnley; Spencer Gordon; Ruta Mehta; Rahul Savani

doi:10.1016/j.jcss.2020.05.007

Unique end of potential line

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	1-35
Number of pages	35
Journal	Journal of Computer and System Sciences
Volume	114
DOIs	https://doi.org/10.1016/j.jcss.2020.05.007
State	Published - Dec 2020

Keywords

Continuous local search
Contraction map
P-matrix Linear Complementarity Problem
TFNP
Total search problems
Unique sink orientation

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Online availability

10.1016/j.jcss.2020.05.007

Library availability

Discover UIUC Full Text

Cite this

@article{5441e81f54e04072bd0bf8920ea44e92,

title = "Unique end of potential line",

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.",

keywords = "Continuous local search, Contraction map, P-matrix Linear Complementarity Problem, TFNP, Total search problems, Unique sink orientation",

author = "John Fearnley and Spencer Gordon and Ruta Mehta and Rahul Savani",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = dec,

doi = "10.1016/j.jcss.2020.05.007",

language = "English (US)",

volume = "114",

pages = "1--35",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Unique end of potential line

AU - Fearnley, John

AU - Gordon, Spencer

AU - Mehta, Ruta

AU - Savani, Rahul

PY - 2020/12

Y1 - 2020/12

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

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

KW - Continuous local search

KW - Contraction map

KW - P-matrix Linear Complementarity Problem

KW - TFNP

KW - Total search problems

KW - Unique sink orientation

UR - http://www.scopus.com/inward/record.url?scp=85085735916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085735916&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2020.05.007

DO - 10.1016/j.jcss.2020.05.007

M3 - Article

AN - SCOPUS:85085735916

SN - 0022-0000

VL - 114

SP - 1

EP - 35

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Unique end of potential line

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this