Unique end of potential line

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)1-35
Number of pages35
JournalJournal of Computer and System Sciences
Volume114
DOIs
StatePublished - 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
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Unique end of potential line'. Together they form a unique fingerprint.

Cite this