Next:
MS3 MINIMUM TREE
Up:
Miscellaneous
Previous:
MS1 MAXIMUM BETWEENNESS
-
I
NSTANCE
:
Linear binary code
C
of length
n
and a string
x
of length
n
.
-
S
OLUTION
:
A codeword
y
of
C
.
-
M
EASURE
:
The Hamming distance between
x
and
y
, i.e.,
d(x,y)
.
-
Bad News:
Not in A
PX
[
21
].
-
Comment:
Not approximable within
for any
unless NP
QP [
22
].
The complementary maximization problem, where the number of bits that
agree between
x
and
y
is to be maximized, does not admit a
PTAS [
289
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997