Abstract: Monica Tataram

REDUCING THE TIME-COST OF ALGORITHMS AT ANY COST

 

This presentation aims at providing a review of various techniques and methods that can be employed for the purpose of reducing – even with a small fraction – the time complexity of some of the most "famous" algorithms that solve NP-complete decision or optimization problems: the SAT problem, the Clique problem, the knapsack problem and so on. These techniques have evolved from the combination of some the well-known algorithms' design methods (divide et impera, dynamic programming, branch-and-bound, local search etc.) with various new approaches and ideas (pseudo-polynomial time algorithms, parameterized complexity, lowering the worst case exponential complexity etc.).