de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
Dumrauf, Dominic: On the hardness of computing local optima. 2011
Inhalt
Introduction
Optimization Problems, Intractability, and Approximation
Standard Set Problems
Satisfiability Problems
Approximation of Intractable Problems
Local Search
The Concept of Local Search
Successful Applications of Local Search
A Framework to Investigate the Complexity of Local Search
Local Search and Game Theory: Optimization in Competition
The Class of Congestion Games
Central Questions of this Thesis
Superior Questions
Restricted Network Congestion Games
Maximum Constraint Assignment
Weighted Standard Set Problems
Publications
Roadmap of this Thesis
Notation
PLS, Reductions, and Completeness
PLS Problems Considered in this Thesis
Basic PLS Problems
Restricted Network Congestion Games
Local Search Versions of Generalized Maximum Satisfiability Problems
Local Search Versions of Weighted Standard Set Problems
Related Work
Early Results
Circuit/Flip
Traveling Salesman Problem
MaxCut
Local Search Versions of Satisfiability Problems
Weighted Set Problems and Graph Problems
Recent Results and the Connection to Game Theory
Computing Nash Equilibria in Unweighted Congestion Games
Approximate Nash Equilibria in Unweighted Congestion Games
Player-Specific (Singleton) Congestion Games
Symmetric Singleton Congestion Games
Related: Equilibrium Search and PPAD
Our Contribution
Computing Nash Equilibria in Two-Player Restricted Network Congestion Games
On the PLS-Complexity of Maximum Constraint Assignment
On the Complexity of Local Search for Weighted Standard Set Problems
A Note on the Presentation of Our Reductions
Computing Nash Equilibria in Two-Player Restricted Network Congestion Games
The Complexity of (2)-RUNCG and (2)-RDNCG
The Network and the Reduction in a Nutshell
The Reduction
Proving the Correctness and Tightness of the Reduction
Conclusion and a Discussion of Questions 4 and 5
On the PLS-Complexity of Maximum Constraint Assignment
On the Relation of Maximum Constraint Assignment to Minimum Constraint Assignment
The General Method for the Intractability Proofs of (3,2,3)-MCA3-par and (2,3,6)-MCA2-par
The Setting
The Idea in a Nutshell
Assumptions and Notation for Circuit/Flip
The Concept of Propagation Trees
(3,2,3)-MCA3-par is Tight PLS-Complete
The Set of Constraints
The Set of Variables
The Constraint-Graph of Our Reduction
A More Detailed Overview of the Reduction
The Set of Predicates
Proving the Correctness and Tightness of the Reduction
(2,3,6)-MCA2-par is Tight PLS-Complete
The Set of Constraints
The Set of Variables
Similarities and Differences to our Reduction in Section 6.3
The Modified Constraint-Graph of Our Reduction
The Set of Modified Predicates
Proving the Correctness and Tightness of the Reduction
A Reduction to Binary Logic
The Reduction
Proving the Correctness and Tightness of the Reduction
Conclusion and a Discussion of Question 6
On the Complexity of Local Search for Weighted Standard Set Problems
How to Show Intractability of Weighted Standard Set Problems
Neighborhoods, Weights, and Tractability
The General Technique of Our Reductions
The PLS-Complexity of Weighted Standard Set Problems
Assumptions and Preliminaries
On the Complexity of Weighted-3-DimensionalMatching-(p,q) and Exact-Cover-By-3-Sets-(k)
The Exact Complexity of SetPacking-(k)
On the Complexity of SetSplitting-(k)
The Exact Complexity of SetCover-(k)
On the Complexity of TestSet-(k)
On the Complexity of SetBasis-(k)
On the Complexity of HittingSet-(k)
On the Complexity of IntersectionPattern-(k)
On the Complexity of ComparativeContainment-(k)
Proving the Tightness of the Reductions
On the Tractability of Weighted Standard Set Problems
Conclusion and a Discussion of Question 7
Conclusion and Directions for Further Research
General Conclusion and a Discussion of Questions 1–3
Settling the PLS-Complexity of the Problems Considered in this Thesis
A Note on the General Structure of Our PLS Reductions
Possible Sources of Intractability in Our PLS-Complete Problems
Open Problems
Combinatorial Optimization
Game Theory
Smoothed Complexity
What is There to Take Home?
Bibliography
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.