5
$\begingroup$

Suppose we have a set $A$ of binary numbers with the same length $n$. For example (with $n=8$):

$A = \{ 10010011, 01011011, 00010010, 11110001\}$

Now, I want to find the binary number $z$ (also with $n$ bits) such that the minimum hamming distance between $z$ and any of these numbers is maximized.

i.e. $z = \arg \max \{ d(x,A) \mid x \in X\}$

with

$d(x,A) := \min \{ d(x,a) \mid a \in A\}$

where $X$ is the set of all $n$-bit binary numbers, and $d(x,a)$ the hamming distance between $x$ and $a$.

Is there any efficient algorithm for this?

Obviously, if $n$ is small enough we can brute-force this, but I'm looking for something more efficient when $n$ is large. The size of $A$, on the other hand, can be assumed relatively small, so any algorithm polynomial in $|A|$ is fine. Also, it does not have to be an exact algorithm. Any algorithm that approximates the correct answer is welcome too.

$\endgroup$
  • $\begingroup$ If all your numbers are 8 bits long, you can just check all possibilities. $\endgroup$ – Yuval Filmus Apr 2 at 15:09
  • $\begingroup$ @YuvalFilmus yes, but see my update. $\endgroup$ – Math-E-Mad-X Apr 2 at 16:19
  • $\begingroup$ Start weeding out bits with one value, only (xxxFxTxx, in your example). Set bits with a clear minority value to that (xxtFtTff): probably, the values with maximal minimum Hamming distance end with 101100. Construct a counter example. $\endgroup$ – greybeard Apr 3 at 6:31
  • $\begingroup$ @greybeard: A counterexample: 10001 (and 01001, and 00101, and 00011) all have minimum distance 2 from $\{01111, 11101, 11011, 10111, 00000\}$ despite making two non-minority-digit choices, while 00000 (from always choosing the minority digit) has minimum distance 0. $\endgroup$ – j_random_hacker Apr 3 at 11:35
2
$\begingroup$

Here is the decision version of the problem, which we can the problem of farthest string.

Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\ge k$ for all $i$.

There is the problem of closest string.

Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\le k$ for all $i$.

Farthest string is dual to closest string.

Let $c$ denote the map that changes a binary string to its 1's complement, i.e., switching 0 and 1 everywhere. For example, $c(010010111)=101101000$. Note that $c\circ c = Id$.

Given an instance of farthest string $(m, n, s_1, s_2, \cdots, s_m, k, s)$, we can construct an instance of closest string $(m, n, c(s_1), c(s_2), \cdots, c(s_m), n-k, s)$. Call this transformation of instances $r$.

For every string $s$ of length $n$, $$d(s,s_i)+d(s, c(s_i))=n.$$ Hence $$d(s,s_i)\ge k\text{ for all }i\ \Longleftrightarrow\ d(s,c(s_i))\le n-k\text{ for all }i. $$

So $r$ converts a yes-instance of farthest string to a yes-instance of closest string. Symmetrically, $r$ converts a yes-instance of closest string to a yes-instance of furthest string. Furthermore, $r\circ r= Id$.

So $r$ is a linear duality reduction between farthest string and closest string.

All results about closest string are about farthest string.

That is because of the duality reduction. Now we can dive into the Wikipedia article on closest string to see find what we have about closest string.

In particular, we know that farthest string is NP-complete. We can check approximability, fixed-parameter tractability as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.