moteur de recherche

Séminaire Algo - Henning Fernau
Séminaire Algo - Henning Fernau
6-Apr-2021 14:00
Age: 15 days

Henning Fernau

Abundant Extensions

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Abstract: Most algorithmic techniques dealing with constructing solutions to combinatorial problems build solutions in an incremental fashion. Often, the whole procedure could be visualized by means of a search tree. To the leaves of such a search tree, we can associate solutions, while to the inner nodes, only pre-solutions can be associated. By looking at all leaves of the search tree, an optimum solution can be found if desired. In particular for reasons of speed, it is crucial to prune off potential branches of the search tree by deciding at an early stage if a certain pre-solution can be ever extended to a solution that is optimal. But, how easy is it to tell if such pruning is possible?

In this survey talk, we first present motivating examples as an introduction, followed by a general framework for extension problems. Then we show that such problems are really abundant, and these examples also prove that the complexity of these extension problems can be the same as or different from that of the original combinatorial question.

<- Back to: Accueil