Constantin Seebach

(AG Algoritms and Complexity, Prof. Schweitzer)
hosted by PhD Program in CS @ TU KL

"Exponential Time Algorithms for Easy Problems"

Algorithms with exponential running times are the best we currently have for NP-complete problems like the satisfiability problem SAT. Analyzing and improving such algorithms is an ongoing area of theoretical research, with important implications for practice, since many interesting problems are NP-complete. This analysis can be taken in a different direction, by taking common exponential algorithm paradigms, like branching on local structures, and applying them to problems which are known to be solvable in polynomial time, i.e. easy problems. This counter-intuitive approach leads to new insights about the power of exponential time algorithms. Upper bounds as well as lower bounds can be shown for various easy problems in this algorithmic framework.

Time:	Monday, 22.02.2021, 15:45
Place:
Video:

Termin als Datei downloaden und in den Kalender importieren.