Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1119-1125. https://doi.org/10.24963/ijcai.2020/156
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.
Constraints and SAT: Constraint Optimization
Constraints and SAT: Constraint Satisfaction