Diversity in Combinatorial Optimization
share
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.
READ FULL TEXT