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 introduce 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. Going further, we devise a framework to translate kernels of a certain type for a given combinatorial problem X into kernels of a slightly larger size for its diverse version. |
Year | Venue | DocType |
---|---|---|
2019 | arXiv: Data Structures and Algorithms | Journal |
Volume | Citations | PageRank |
abs/1903.07410 | 0 | 0.34 |
References | Authors | |
18 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julien Baste | 1 | 18 | 10.17 |
Michael R. Fellows | 2 | 4138 | 319.37 |
Lars Jaffke | 3 | 9 | 4.03 |
Tomás Masarík | 4 | 0 | 1.01 |
Mateus de Oliveira Oliveira | 5 | 0 | 1.69 |
Geevarghese Philip | 6 | 0 | 1.01 |
Frances A. Rosamond | 7 | 97 | 7.77 |