> Details

Fearnley, John [Author]; Gordon, Spencer [Author]; Mehta, Ruta [Author]; Savani, Rahul [Author] ; John Fearnley and Spencer Gordon and Ruta Mehta and Rahul Savani [Contributor]

Unique End of Potential Line

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Unique End of Potential Line
  • Contributor: Fearnley, John [Author]; Gordon, Spencer [Author]; Mehta, Ruta [Author]; Savani, Rahul [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ICALP.2019.56
  • Keywords: contraction map ; total search problems ; P-matrix linear complementarity problem ; continuous local search ; TFNP ; unique sink orientation
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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 Point of Contraction Maps, and solving Unique Sink Orientations (USOs). UniqueEOPL seems to a proper subclass of CLS and looks more likely to be the right class for the problems of interest. We identify a problem - closely related to solving contraction maps and USOs - that is complete for UniqueEOPL. Our results also give the fastest randomised algorithm for P-matrix LCP.
  • Access State: Open Access