Unique end of potential line

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period7/9/197/12/19

Keywords

  • Continuous local search
  • Contraction map
  • P-matrix linear complementarity problem
  • TFNP
  • Total search problems
  • Unique sink orientation

ASJC Scopus subject areas

  • Software

Cite this

Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2019). Unique end of potential line. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [56] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2019.56

Unique end of potential line. / Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul.

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. ed. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 56 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Fearnley, J, Gordon, S, Mehta, R & Savani, R 2019, Unique end of potential line. in C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (eds), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019., 56, Leibniz International Proceedings in Informatics, LIPIcs, vol. 132, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, 7/9/19. https://doi.org/10.4230/LIPIcs.ICALP.2019.56
Fearnley J, Gordon S, Mehta R, Savani R. Unique end of potential line. In Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 56. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.ICALP.2019.56
Fearnley, John ; Gordon, Spencer ; Mehta, Ruta ; Savani, Rahul. / Unique end of potential line. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. editor / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).
@inproceedings{96d903d82fa543b58a90bb2d18f427b0,
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 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.",
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",
year = "2019",
month = "7",
day = "1",
doi = "10.4230/LIPIcs.ICALP.2019.56",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",
booktitle = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019",

}

TY - GEN

T1 - Unique end of potential line

AU - Fearnley, John

AU - Gordon, Spencer

AU - Mehta, Ruta

AU - Savani, Rahul

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

ER -