[edit]

# Maximization of Minimum Weighted Hamming Distance between Set Pairs

*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}$.