Benutzer: Gast  Login
Titel:

On the Smoothed Complexity of Combinatorial Local Search

Dokumenttyp:
Konferenzbeitrag
Autor(en):
Giannakopoulos, Yiannis; Grosz, Alexander; Melissourgos, Themistoklis
Nicht-TUM Koautoren:
ja
Kooperation:
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...     »
Stichworte:
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
Kongress- / Buchtitel:
The 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP)
Kongress / Zusatzinformationen:
Tallinn, Estonia
Verlag / Institution:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Jahr:
2024
Monat:
Jul
Seiten:
19
Sprache:
en
Volltext / DOI:
doi:10.4230/LIPICS.ICALP.2024.72
Key publication:
Ja
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
commissioned:
not commissioned
Interdisziplinarität:
Nein
Leitbild:
;
Technology:
Nein
Ethics und Sustainability:
Nein
 BibTeX