1069. Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
Invited abstract in session WD-17: Diversity in Solutions to CO problems, stream Combinatorial Optimization.
Wednesday, 14:30-16:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Andres Lopez Martinez
|
| Mathematics and Computer Science, Eindhoven University of Technology | |
| 2. | Mark de Berg
|
| Eindhoven University of Technology | |
| 3. | Frits Spieksma
|
| Mathematics and Computer Science, Eindhoven University of Technology |
Abstract
We consider the problem of finding diverse solutions to combinatorial problems whose solution sets form a distributive lattice structure. We identify three structural conditions that, when met by a problem, ensure that a k-sized multiset of maximally-diverse solutions—measured by the sum of pairwise Hamming distances—can be found in polynomial time. We apply this framework to obtain polynomial time algorithms for finding diverse minimum s-t cuts, diverse stable matchings, and diverse circulations in planar graphs. We also show that the framework extends to two other natural diversity measures.
Keywords
- Combinatorial Optimization
- Algorithms
- Complexity and Approximation
Status: accepted
Back to the list of papers