Closest string

To understand the word "center", it is necessary to define a distance between two strings.

Instances of closest string may contain information that is not essential to the problem.

In some sense, the usual input of closest string contains information, that does not contribute to the hardness of the problem.

For example, if some strings contain the character a, but none contains the character z, replacing all as with zs would yield an essentially equivalent instance, that is: from a solution of the modified instance, the original solution can be restored, and vice versa.

When all input strings that share the same length are written on top of each other, they form a matrix.

That means, if we permute all input strings according to a certain permutation π and obtain a solution string s to that modified instance, then π−1(s) will be a solution to the original instance.

Li et al. evolved a polynomial-time approximation scheme[3] which is practically unusable because of the large hidden constants.