Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17633 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916706294693888 |
|---|---|
| author | Iwamasa, Yuni Matsuda, Tomoki Morihira, Shunya Sumita, Hanna |
| author_facet | Iwamasa, Yuni Matsuda, Tomoki Morihira, Shunya Sumita, Hanna |
| contents | In this paper, we present a general framework for efficiently computing diverse solutions to combinatorial optimization problems. Given a problem instance, the goal is to find $k$ solutions that maximize a specified diversity measure; the sum of pairwise Hamming distances or the size of the union of the $k$ solutions. Our framework applies to problems satisfying two structural properties: (i) All solutions are of equal size and (ii) the family of all solutions can be represented by a surjection from the family of ideals of some finite poset. Under these conditions, we show that the problem of computing $k$ diverse solutions can be reduced to the minimum cost flow problem and the maximum $s$-$t$ flow problem. As applications, we demonstrate that both the unweighted minimum $s$-$t$ cut problem and the stable matching problem satisfy the requirements of our framework. By utilizing the recent advances in network flows algorithms, we improve the previously known time complexities of the diverse problems, which were based on submodular function minimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17633 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A general framework for finding diverse solutions via network flow and its applications Iwamasa, Yuni Matsuda, Tomoki Morihira, Shunya Sumita, Hanna Data Structures and Algorithms Computational Complexity In this paper, we present a general framework for efficiently computing diverse solutions to combinatorial optimization problems. Given a problem instance, the goal is to find $k$ solutions that maximize a specified diversity measure; the sum of pairwise Hamming distances or the size of the union of the $k$ solutions. Our framework applies to problems satisfying two structural properties: (i) All solutions are of equal size and (ii) the family of all solutions can be represented by a surjection from the family of ideals of some finite poset. Under these conditions, we show that the problem of computing $k$ diverse solutions can be reduced to the minimum cost flow problem and the maximum $s$-$t$ flow problem. As applications, we demonstrate that both the unweighted minimum $s$-$t$ cut problem and the stable matching problem satisfy the requirements of our framework. By utilizing the recent advances in network flows algorithms, we improve the previously known time complexities of the diverse problems, which were based on submodular function minimization. |
| title | A general framework for finding diverse solutions via network flow and its applications |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2504.17633 |