Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top