Trova il numero binario con una distanza massima di martello WRT dato un set di numeri binari

Question

Supponiamo di avere un set $ A $ di numeri binari con la stessa lunghezza $ n $. Per esempio (con $ n = 8 $):

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

Ora, voglio trovare il numero binario $ z $ (anche con $ n $ bit) in modo tale che la distanza minima di keting tra $ z $ e uno di questi numeri è massimizzato.

cioè $ z = arg max {d (x, a) mid x in x } $

insieme a

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

dove $ X $ è l'insieme di tutti $ n $-bit numeri binari e $ d (x, a) $ la distanza di Hamming tra $ x $ e $ a $.

Esiste un algoritmo efficiente per questo?

Ovviamente, se $ n $ è abbastanza piccolo che possiamo forzare questo, ma sto cercando qualcosa di più efficiente quando $ n $ è grande. La dimensione di $ A $, d'altra parte, può essere assunto relativamente piccolo, quindi qualsiasi polinomio algoritmo in $ | A | $ è ok. Inoltre, non deve essere un algoritmo esatto. Anche qualsiasi algoritmo che si avvicina alla risposta corretta è il benvenuto.