Next:
MS2 NEAREST CODEWORD
Up:
Miscellaneous
Previous:
Miscellaneous
-
I
NSTANCE
:
Finite set
A
, collection
C
of ordered triples
(a,b,c)
of
distinct elements from
A
.
-
S
OLUTION
:
A one-to-one function
.
-
M
EASURE
:
Number of triples where either
f(a)<f(b)<f(c)
or
f(c)<f(b)<f(a)
.
-
Good News:
Approximable within 2 [
74
].
-
Bad News:
A
PX
-complete [
74
].
-
Comment:
Admits a PTAS if
[
23
].
-
Garey and Johnson:
MS1
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997