User: Guest  Login
Title:

On the Smoothed Complexity of Combinatorial Local Search

Document type:
Konferenzbeitrag
Author(s):
Giannakopoulos, Yiannis; Grosz, Alexander; Melissourgos, Themistoklis
Non-TUM Co-author(s):
ja
Cooperation:
international
Abstract:
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems, and show how a diverse selection of problems within the complexity class PLS can be cast within this model. This abstraction allows us to identify key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. We formalize this via a black-box tool that provides concrete bounds on the expected maximum number of steps needed until local s...     »
Keywords:
Smoothed Analysis, local search, better-response dynamics, PLS-hardness, combinatorial local optimization, congestion games, pure Nash equilibria, Theory of computation → Algorithmic game theory, Mathematics of computing → Combinatorial optimization, Theory of computation → Computational complexity and cryptography
Intellectual Contribution:
Discipline-based Research
Book / Congress title:
The 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP)
Congress (additional information):
Tallinn, Estonia
Publisher:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Year:
2024
Month:
Jul
Pages:
19
Language:
en
Fulltext / DOI:
doi:10.4230/LIPICS.ICALP.2024.72
Key publication:
Ja
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
Commissioned:
not commissioned
Technology:
Nein
Interdisciplinarity:
Nein
Mission statement:
;
Ethics and Sustainability:
Nein
 BibTeX