Max-Distance Sparsification for Diversification and Clustering
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915360442155008 |
|---|---|
| author | Kumabe, Soh |
| author_facet | Kumabe, Soh |
| contents | Let $\mathcal{D}$ be a set family that is the solution domain of some combinatorial problem. The \emph{max-min diversification problem on $\mathcal{D}$} is the problem to select $k$ sets from $\mathcal{D}$ such that the Hamming distance between any two selected sets is at least $d$. FPT algorithms parameterized by $k+\ell $, where $\ell=\max_{D\in \mathcal{D}}|D|$, and $k+d$ have been actively studied recently for several specific domains.
This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization $k+\ell $ and $k+d$, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to $\mathcal{D}$. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains $\mathcal{D}$, including the domain of $t$-linear matroid intersection, almost $2$-SAT, minimum edge $s,t$-flows, vertex sets of $s,t$-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results.
Our main technical breakthrough is introducing the notion of \emph{max-distance sparsifier} of $\mathcal{D}$, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain $\mathcal{D}$. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of $\mathcal{D}$. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on $\mathcal{D}$, as well as $k$-center and $k$-sum-of-radii clustering problems on $\mathcal{D}$, which are also natural problems in the context of diversification and have their own interests. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02845 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Max-Distance Sparsification for Diversification and Clustering Kumabe, Soh Data Structures and Algorithms Let $\mathcal{D}$ be a set family that is the solution domain of some combinatorial problem. The \emph{max-min diversification problem on $\mathcal{D}$} is the problem to select $k$ sets from $\mathcal{D}$ such that the Hamming distance between any two selected sets is at least $d$. FPT algorithms parameterized by $k+\ell $, where $\ell=\max_{D\in \mathcal{D}}|D|$, and $k+d$ have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization $k+\ell $ and $k+d$, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to $\mathcal{D}$. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains $\mathcal{D}$, including the domain of $t$-linear matroid intersection, almost $2$-SAT, minimum edge $s,t$-flows, vertex sets of $s,t$-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of \emph{max-distance sparsifier} of $\mathcal{D}$, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain $\mathcal{D}$. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of $\mathcal{D}$. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on $\mathcal{D}$, as well as $k$-center and $k$-sum-of-radii clustering problems on $\mathcal{D}$, which are also natural problems in the context of diversification and have their own interests. |
| title | Max-Distance Sparsification for Diversification and Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.02845 |