Maximization of Minimum Weighted Hamming Distance between Set Pairs

Tatsuya Matsuoka, Shinji Ito
Proceedings of the 15th Asian Conference on Machine Learning, PMLR 222:895-910, 2024.

Abstract

\emph{Finding diverse solutions} to combinatorial optimization problems is beneficial for a deeper understanding of complicated real-world problems and for simpler and more practical mathematical modeling. For this purpose, it is desirable that every solution is far away from one another and that solutions can be found in time not depending polynomially on the size of the family of feasible solutions. In this paper, we investigate the problem of finding diverse sets in the sense of maximizing the \emph{minimum} of \emph{weighted Hamming distance} between \emph{set pairs}. Under a particular assumption, we provide an algorithm that gives diverse sets of almost $\mu /2$-approximation in expectation in the sense of maximization of the minimum of the expected value, where $\mu \in [0, 1]$ is a parameter on a subroutine. We further give a hardness result that any approximation ratio better than $2/3$ is impossible in polynomial time under the assumption of $\mathrm{P} \neq \mathrm{NP}$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v222-matsuoka24a, title = {Maximization of Minimum Weighted Hamming Distance between Set Pairs}, author = {Matsuoka, Tatsuya and Ito, Shinji}, booktitle = {Proceedings of the 15th Asian Conference on Machine Learning}, pages = {895--910}, year = {2024}, editor = {Yanıkoğlu, Berrin and Buntine, Wray}, volume = {222}, series = {Proceedings of Machine Learning Research}, month = {11--14 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v222/matsuoka24a/matsuoka24a.pdf}, url = {https://proceedings.mlr.press/v222/matsuoka24a.html}, abstract = {\emph{Finding diverse solutions} to combinatorial optimization problems is beneficial for a deeper understanding of complicated real-world problems and for simpler and more practical mathematical modeling. For this purpose, it is desirable that every solution is far away from one another and that solutions can be found in time not depending polynomially on the size of the family of feasible solutions. In this paper, we investigate the problem of finding diverse sets in the sense of maximizing the \emph{minimum} of \emph{weighted Hamming distance} between \emph{set pairs}. Under a particular assumption, we provide an algorithm that gives diverse sets of almost $\mu /2$-approximation in expectation in the sense of maximization of the minimum of the expected value, where $\mu \in [0, 1]$ is a parameter on a subroutine. We further give a hardness result that any approximation ratio better than $2/3$ is impossible in polynomial time under the assumption of $\mathrm{P} \neq \mathrm{NP}$.} }
Endnote
%0 Conference Paper %T Maximization of Minimum Weighted Hamming Distance between Set Pairs %A Tatsuya Matsuoka %A Shinji Ito %B Proceedings of the 15th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Berrin Yanıkoğlu %E Wray Buntine %F pmlr-v222-matsuoka24a %I PMLR %P 895--910 %U https://proceedings.mlr.press/v222/matsuoka24a.html %V 222 %X \emph{Finding diverse solutions} to combinatorial optimization problems is beneficial for a deeper understanding of complicated real-world problems and for simpler and more practical mathematical modeling. For this purpose, it is desirable that every solution is far away from one another and that solutions can be found in time not depending polynomially on the size of the family of feasible solutions. In this paper, we investigate the problem of finding diverse sets in the sense of maximizing the \emph{minimum} of \emph{weighted Hamming distance} between \emph{set pairs}. Under a particular assumption, we provide an algorithm that gives diverse sets of almost $\mu /2$-approximation in expectation in the sense of maximization of the minimum of the expected value, where $\mu \in [0, 1]$ is a parameter on a subroutine. We further give a hardness result that any approximation ratio better than $2/3$ is impossible in polynomial time under the assumption of $\mathrm{P} \neq \mathrm{NP}$.
APA
Matsuoka, T. & Ito, S.. (2024). Maximization of Minimum Weighted Hamming Distance between Set Pairs. Proceedings of the 15th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 222:895-910 Available from https://proceedings.mlr.press/v222/matsuoka24a.html.

Related Material