Title
Diversity in Combinatorial Optimization.
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