Next:
MP8 MINIMUM PLANAR
Up:
Mathematical Programming
Previous:
MP6 MINIMUM GENERALIZED
MP7 M
INIMUM
Q
UADRATIC
0-1 A
SSIGNMENT
I
NSTANCE
: Nonnegative integer
-matrix
, nonnegative integer
-matrix
.
S
OLUTION
: Binary
-matrix
such that there is at most one 1 in each row of
X
and exactly one 1 in each column of
X
.
M
EASURE
:
.
Bad News:
Not in A
PX
[
313
].
Comment:
Not in A
PX
even if
D
satisfies the triangle inequality [
302
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
-matrix
,
nonnegative integer
-matrix
.
-matrix
such that there is at
most one 1 in each row of
X
and exactly one 1 in each column of
X
.
.