Charles Explorer logo
🇨🇿

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

Publikace na Matematicko-fyzikální fakulta |
2020

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory.

We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X.

Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.