Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2504.02369 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916672683638784 |
|---|---|
| author | de Berg, Mark Martínez, Andrés López Spieksma, Frits |
| author_facet | de Berg, Mark Martínez, Andrés López Spieksma, Frits |
| contents | We generalize the polynomial-time solvability of $k$-\textsc{Diverse Minimum s-t Cuts} (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets have 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 and diverse stable matchings. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02369 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure de Berg, Mark Martínez, Andrés López Spieksma, Frits Data Structures and Algorithms Computational Complexity We generalize the polynomial-time solvability of $k$-\textsc{Diverse Minimum s-t Cuts} (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets have 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 and diverse stable matchings. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions. |
| title | Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2504.02369 |