Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.56
URN: urn:nbn:de:0030-drops-106327
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10632/
Fearnley, John ; Gordon, Spencer ; Mehta, Ruta ; Savani, Rahul
Unique End of Potential Line
| pdf-format: |
|
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 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.
BibTeX - Entry
@InProceedings{fearnley_et_al:LIPIcs:2019:10632,
author = {John Fearnley and Spencer Gordon and Ruta Mehta and Rahul Savani},
title = {{Unique End of Potential Line}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10632},
URN = {urn:nbn:de:0030-drops-106327},
doi = {10.4230/LIPIcs.ICALP.2019.56},
annote = {Keywords: P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search}
}
| Keywords: | P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search | |
| Seminar: | 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.07.2019 |
