TY - GEN
T1 - Unique end of potential line
AU - Fearnley, John
AU - Gordon, Spencer
AU - Mehta, Ruta
AU - Savani, Rahul
N1 - Publisher Copyright:
© Graham Cormode, Jacques Dark, and Christian Konrad; licensed under Creative Commons License CC-BY
PY - 2019/7/1
Y1 - 2019/7/1
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 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.
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 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.
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=85069203086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069203086&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2019.56
DO - 10.4230/LIPIcs.ICALP.2019.56
M3 - Conference contribution
AN - SCOPUS:85069203086
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
A2 - Baier, Christel
A2 - Chatzigiannakis, Ioannis
A2 - Flocchini, Paola
A2 - Leonardi, Stefano
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Y2 - 9 July 2019 through 12 July 2019
ER -