Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
复制标题
DOI：
10.1016/j.artint.2021.103644
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Julien Baste;M. Fellows;L. Jaffke;Tomáš Masařík;Mateus de Oliveira Oliveira-Mateus-de-Oliveira-Oliveira-2613196;Geevarghese Philip;Frances A. Rosamond
中科院分区：
文献类型：
--
作者：
Julien Baste;M. Fellows;L. Jaffke;Tomáš Masařík;Mateus de Oliveira Oliveira-Mateus-de-Oliveira-Oliveira-2613196;Geevarghese Philip;Frances A. Rosamond
当将具有实际相关性的应用建模为组合问题X的实例时，我们通常感兴趣的不仅是为该实例找到一个最佳解决方案，而且是找到足够多样化的良好解决方案的集合。在这项工作中，我们从固定参数易处理性理论的角度出发，对多样性进行了系统的研究。首先，我们考虑一个直观的概念ofdiversity的集合的解决方案，适合各种各样的组合问题的实际利益。然后，我们提出了一个算法框架，自动转换为一个给定的组合问题X的动态规划算法的不同版本的X树分解为基础的动态规划算法。令人惊讶的是，我们的算法有一个多项式依赖的多样性参数。
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in findingoneoptimal solution for that instance, but in finding asufficiently diversecollection of good solutions. In this work we initiate a systematic study ofdiversityfrom the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion ofdiversityof a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present 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.