Trouver le numéro binaire avec une distance maximale Hamming WRT donnée un ensemble de nombres binaires

Question

Supposons que nous ayons un ensemble $ A $ de nombres binaires avec la même longueur $ n $. Par exemple (avec $ n = 8 $):

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

Maintenant, je veux trouver le numéro binaire $ z $ (également avec $ n $ bits) de telle sorte que la distance minimale entre $ z $ et l'un de ces nombres est maximisé.

c'est à dire $ z = arg max {d (x, a) mid x in x } $

avec

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

où $ X $ est l'ensemble de tous $ n $-bit binaire, et $ d (x, a) $ la distance de Hamming entre $ x $ et $ a $.

Y a-t-il un algorithme efficace pour cela?

De toute évidence, si $ n $ est assez petit, nous pouvons force brute cela, mais je cherche quelque chose de plus efficace quand $ n $ est large. La taille de $ A $, en revanche, peut être supposé relativement petit, donc n'importe quel polynôme d'algorithme en $ | A | $ c'est bien. De plus, il ne doit pas être un algorithme exact. Tout algorithme qui se rapproche de la bonne réponse est également le bienvenu.