Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911454528012288 |
|---|---|
| author | Baste, Julien Fellows, Michael R. Jaffke, Lars Masařík, Tomáš Oliveira, Mateus de Oliveira Philip, Geevarghese Rosamond, Frances A. |
| author_facet | Baste, Julien Fellows, Michael R. Jaffke, Lars Masařík, Tomáš Oliveira, Mateus de Oliveira Philip, Geevarghese Rosamond, Frances A. |
| contents | 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. First, we consider an intuitive notion of diversity of 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_07410 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory Baste, Julien Fellows, Michael R. Jaffke, Lars Masařík, Tomáš Oliveira, Mateus de Oliveira Philip, Geevarghese Rosamond, Frances A. Data Structures and Algorithms Discrete Mathematics 05C85 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. First, we consider an intuitive notion of diversity of 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. |
| title | Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory |
| topic | Data Structures and Algorithms Discrete Mathematics 05C85 |
| url | https://arxiv.org/abs/1903.07410 |