Parameterized Complexity of Local Search

01.03.2011 - 28.02.2013
Research funding project
One of the main goals of theoretical computer science is the employment of mathematical methods to assess the intrinsic difficulty of computational tasks (computational complexity), and to design efficient algorithms. A major discovery in the last quarter of research in theoretical computer science is the existence of computational problems that are inherently hard for algorithmic attacks. Hence serious research goes into finding algorithms for problems that are believed to be intractable. It is desirable that these algorithms have provably good run times and solution quality. These two goals are contradictory and often cannot be achieved simultaneously. For real life problems, algorithms that abandon one or both of these demands are regularly used. Such algorithms are called heuristics. Heuristic algorithms have several disadvantages: they might be able to find good quality solutions on many instances but fail completely on others; they might run reasonably fast on most instances but slack on some singular inputs. Despite these disadvantages, heuristic algorithms are often the most practical approach for solving many intractable optimization problems. The main goal of this project is to search for a mathematical explanation as to why some heuristics work well and why some do not. Such explanations would not only be of theoretical importance, they can bring us to the design of new and better heuristic algorithms which may have a great practical impact. We plan to study a specific kind of heuristic , namely LOCAL SEARCH. The main tools of our study are from Parameterized Complexity, Logic, and Combinatorics. Local search algorithms start with some feasible solution and move towards a better solution (if possible) by performing some locally optimal choices. This is a popular heuristic for several combinatorial optimization problems. There have been some very preliminary results known about when such heuristics result in better solutions. In this work we plan to expand this study to a broader set of problems and hope to get some meta statements about the problems on which local search is expected to yield good quality solutions.

People

Project leader

Project personnel

Institute

Grant funds

  • BM für Wissenschaft, Forschung und Wirtschaft (bm:wfw) (National) Federal Ministry of Science and Research (bm:wf)

Research focus

  • Computational Intelligence: 100%

Keywords

GermanEnglish
AlgorithmenAlgorithms
HeuristikHeuristics
Lokale Suchelocal search
Parametrisierte KomplexitätParameterized Complexity

External partner

  • Institute of Mathematical Sciences

Publications