Exponential time algorithms with applications to scheduling problems

Vincent T’Kindt (Polytech Tours, LI)

October 14, 2015 | 13h00-14h00 | Salle 110 - Polytech Tours

Since the last two decades, Exponential Algorithms started to be the focus of several theoretical studies. Despite the youth of this field of research, several major techniques and results are known for combinatorial optimization problems. After an introduction to Exponential Algorithms (What are they? Interest?), we will see three classic techniques which can be used to derive such algorithms: Dynamic Programming, Branch & Reduce and Sort & Search.