Next:
MP3 MAXIMUM PACKING
Up:
Mathematical Programming
Previous:
MP1 MINIMUM 0-1
MP2 M
AXIMUM
B
OUNDED
0-1 P
ROGRAMMING
I
NSTANCE
: Integer
-matrix
, integer
m
-vector
, nonnegative binary
n
-vector
.
S
OLUTION
: A binary
n
-vector
such that
.
M
EASURE
: The scalar product of
c
and
x
, i.e.,
.
Bad News:
NPO PB-complete [
49
].
Comment:
Transformation from L
ONGEST
P
ATH
WITH
F
ORBIDDEN
P
AIRS
. Not approximable within
[
197
] and not within
for any
[
203
].
Garey and Johnson:
MP1
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
-matrix
, integer
m
-vector
, nonnegative binary
n
-vector
.
such that
.
.
[
197
] and not within
for any
[
203
].