Personal tools
You are here: Home Graduate Study Exact Algorithms for NP-Hard Problems

Exact Algorithms for NP-Hard Problems

NP-hard problems such as Satisfiability, Clique and  Travelling Salesman need to be solved in practice, but there's not much known about solving them more efficiently than brute-force search. In this project, we will seek to improve the state-of-the-art in design and analysis of exact algorithms for these problems. We will be interested in algorithms running in time 2^{n-\delta n} poly(m), where n is the number of variables and m the instance size, and we would like \delta > 0  to be as large as possible. Some algorithms with this kind of running time bound are known for the problems mentioned above, but there is potential for improvement, and also for finding more general analysis techniques for the running time.

 

Potential Supervisor

Rahul Santhanam

Document Actions