Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Abstract
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.
Cite
Text
Baste et al. "Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/156Markdown
[Baste et al. "Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/baste2020ijcai-diversity/) doi:10.24963/IJCAI.2020/156BibTeX
@inproceedings{baste2020ijcai-diversity,
title = {{Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory}},
author = {Baste, Julien and Fellows, Michael R. and Jaffke, Lars and Masarík, Tomás and de Oliveira Oliveira, Mateus and Philip, Geevarghese and Rosamond, Frances A.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1119-1125},
doi = {10.24963/IJCAI.2020/156},
url = {https://mlanthology.org/ijcai/2020/baste2020ijcai-diversity/}
}