6
$\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$
4
  • $\begingroup$ If all your numbers are 8 bits long, you can just check all possibilities. $\endgroup$ Apr 2, 2019 at 15:09
  • $\begingroup$ @YuvalFilmus yes, but see my update. $\endgroup$ Apr 2, 2019 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, 2019 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$ Apr 3, 2019 at 11:35

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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