Next:
MP15 MAXIMUM INTEGER
Up:
Mathematical Programming
Previous:
MP13 MAXIMUM KNAPSACK
MP14 M
AXIMUM
I
NTEGER
M
-D
IMENSIONAL
K
NAPSACK
I
NSTANCE
: Nonnegative integer
-matrix,
, nonnegative integer
m
-vector
, nonnegative integer
n
-vector
.
m
is a constant,
.
S
OLUTION
: Nonnegative integer
n
-vector
such that
.
M
EASURE
: The scalar product of
c
and
x
, i.e.,
.
Good News:
Admits a PTAS [
63
].
Garey and Johnson:
Generalization of MP10
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
-matrix,
,
nonnegative integer
m
-vector
,
nonnegative integer
n
-vector
.
m
is a constant,
.
such that
.
.