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