0
$\begingroup$

A deterministic $(2−2/(k+1))^n$ algorithm for $k$-SAT based on local search

 I have read this paper and I couldn't understand how to culculate the $covering$ $radius$ of a code in the Hamming space. It is defined as follows in the paper.


 We identify assignments with binary words. The set of these words of length $n$ is the $Hamming$ $space$ denoted by $H_n=\{0,1\}^n$. The $Hamming$ $distance$ between two assignments is the number of positions in which these two assignments differ. The $ball$ of radius $r$ around an assignment $a$ is the set of all assignments whose Hamming distance to $a$ is at most $r$.
 A $code$ of length $n$ is simply a subset of $H_n$. The $covering$ $radius$ $r$ of a code $C$ is defined by $$r=\max_{u∈\{0,1\}^n}\min_{v∈C }d(u,v),$$ where $d(u,v)$ denotes the Hamming distance between $u$ and $v$.


 The $\max$ of $\min$ is exactly the point I couldn't calculate. So I considered the instance of $C$ and tried to calculate its covering radius.

e.g.)$$C=\{000,010,011,100,101,110\}⊆H_3$$             enter image description here

 In this case, how can I calculate the covering radius $r$?

$\endgroup$
  • $\begingroup$ Note you should use *asterisks* to typeset italics in this site (instead of hacking it with LaTeX). $\endgroup$ – dkaeae Jul 8 at 7:43
  • $\begingroup$ I didn't know that. I'm sorry for not knowing it. I'll use asterisks from now on. $\endgroup$ – NEUTRON Jul 8 at 8:31
1
$\begingroup$

It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is max(1,1)=1

Overall, the algorithm is the following:

  • for each possible code x, find the closest element c in C (i.e. the one with minimum distance d(x,c)) and record this distance
  • find the maximum of all distances recorded at the previous step

I find that it's well visualized with set of spheres covering part of 3D space. You check all points outside of spheres and find one that has the largest distance to its closest sphere.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your detailed answer. Now I can calculate the covering radius not only in this case but also in other general case. And the visualization mentioned in the last really helped my understanding. Now I know the covering radius stands for how large the radius of each code in C should be to cover whole words in Hn. $\endgroup$ – NEUTRON Jul 8 at 15:43

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.