Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
416
Chapter
26.
Operations
on
Valid Inequalities
and
Facets
this
way some new facet of
CUT
n
+1
starting
from a given facet of
CUT
n
.
The
next
lemma
contains a set of conditions
that
are sufficient for achieving
this
goal.
LeIllIna
26.5.3.
(Lifting
LeIllIna)
Let
v E
Jm.E
n
and
v'
E Jm.En+l. Suppose that
the following assertions hold.
(i) The inequality v
T
x
:::;
0 is facet
inducing
for
CUTn
and the inequality
(v')T
x:::;
0 is valid
for
CUT
n
+1'
(ii) There exist
G)
-1
subsets
8j
of
{2, 3,
...
,n}
such that the cut vectors
8(8j)
(in
Kn)
are linearly independent roots
of
v
T
x
:::;
0 and the cut vectors
8(8j)
(in
K
n
+
1
)
are roots
of
(v')T
x
:::;
O.
(iii) There exist n subsets Tk
of
{2, 3,
...
,n,
n +
I}
with n + 1 E Tk such that
the cut vectors 8(Tk)
(in
K
n
+1)
are roots
of
(v')T
x
:::;
0 and the incidence
vectors
of
the sets Tk are linearly independent.
Then, the inequality
(v')T
x
:::;
0 is facet inducing
for
CUT
n+1'
Proof.
It
suffices
to
check
that
the
(ntl)
- 1
cut
vectors
8(8j)
and
8(Tk) are
linearly
independent.
This
can
be done
in
the
same
way as
in
the
proof
of
Theorem
26.5.1. I
In
the
sequel,
we
only consider a special case of lifting, known as node split-
ting.
The
node
splitting
operation
is,
in
fact, converse
to
the
collapsing
operation
from Section 26.4;
it
is
defined as follows. Let v E
Jm.E
n
and
v'
E
Jm.E
n
+
1
satisfy
the
conditions:
Vij
=
V~j
Vli
= vii +
v;
n+1
for 2
:::;
i < j
:::;
n,
for 2
:::;
i
:::;
n.
So,
v'is
obtained
from v by
splitting
node
1 into two nodes 1, n + 1
and
corre-
spondingly
splitting
the
edgeweight
Vli
into
vii
and
v;
n+ll
the
other
components
remaining
unchanged.
In
other
words, v comes from
v'
by collapsing
the
nodes 1
and
n + 1 into a single node
1.
In
this
case, if v
T
x
:::;
0
is
facet inducing,
then
the
condition
(ii) of
Lemma
26.5.3
automatically
holds.
In
our
concrete applications
of
the
Lifting
Lemma
26.5.3,
the
condition (i) will hold by
construction
of
v'
and,
therefore,
the
crucial
point
will be to check condition (iii), i.e.,
to
find n
additional
"good" roots.
We will see
in
the
next
sections
many
applications of
the
Lifting
Lemma
26.5.3
and
of
Theorems
26.4.3
and
26.4.4
on
collapsing.
26.6
Facets
by
Projection
We
present
here
another
tool for showing
that
a given valid inequality is facet
defining.
This
method
works when some projections of
the
given inequality have
some
prescribed
properties;
it
is
described by Boissin [1994].
The
result
turns
out
to
have a simpler formulation
in
the
context of correlation polyhedra. So,
we
first
state
it
for correlation
polyhedra
and,
then,
we
reformulate
it
for
cut
polyhedra.
26.6 Facets by
Projection
Observe first
that,
if
an
inequality
L aijPij::;
0:
1::;i::;j
:'On
is
valid for
COR~,
then
its projection
417
on
the
set (of
pairs
including diagonal pairs from)
Vn
\
{n}
is obviously valid
for
CO~_j'
However,
it
may be
that
the
projected inequality defines a facet of
CO~_l
without
the
initial inequality
to
be
facet defining.
This
is
the
case, for
instance, for
the
(nonfacet defining) inequality
Pu
+
P22
2:
0 whose projection
PH
2:
0 is facet defining.
The
next result shows, however,
that
if
we
suppose
that
several projections are facet defining together with some additional conditions,
then
we
can
conclude
that
the
initial inequality
is
facet defining.
Proposition
26.6.1.
Let
W
1
,
...
,
WI.;
~
Vn
such that
Vn
= W
t
U
...
U
WI.;
and
each pair
of
elements
of
Vn
belongs to some Wr (1
:s;
r
:s;
k).
Let
a E
~V"UE"
and
0:
E R Suppose that the following conditions hold.
(i) The inequality aTp
:=
polytope
COR~.
L..J.<i'(i<:n
aijPij
:s;
0:
is valid
for
the correlation
(ii) The graph with node set {I,
...
,
k}
and whose edges
are
the pairs
rs
for
which there exist
i,j
E Wr n Ws such that aij :f 0 is connected.
(iii) For each T = 1,
...
, k, the inequality
'-"::'JI",JI;::",
aijPij
:s;
0:
(obtained as
the projection
of
aT p
:s;
0:
on W
r
)
defines a
of
CORD(W
r
).
Then, the inequality aT P
::;
0:
defines a facet
of
CO~
.
Proof.
Let
b E
~
V"
UE"
,
,8
E
]R
such
that
We
show
that
b =
Aa
and
,8
=
AO:
for some A
ERAs
each vector q E CORD (W
T
)
can
be
extended
to
the
vector
p:=
(q,
0,
...
,0)
of
COR~,
we
deduce
that
From
(iii),
we
obtain
that
there
exists
AT
E
]R
such
that
bij = Araij for
i,j
E W
T
and
,8
Aro:.
We
deduce easily from (ii)
that
all
AT'S
are equal. I
The
following is a reformulation in
the
context
of
cut
polyhedra.
Corollary
26.6.2.
Let WI,
...
)
WI.;
~
Vn
such that
Vn
Wl
U
...
U
WI.;
and
each pair
of
elements
of
Vn
belongs to some W
T
(1
::;
r
::;
k). Let c E ]REn+l and
0:
E R Suppose that the following conditions hold.
418
Chapter
26.
Operations
on
Valid Inequalities
and
Facets
(i)
The inequality c
T
x
CUT~+I'
L.,Jl<::i<j<~n.,f-I
GijXij
::; a is valid for the cut polytope
(ii) The graph with node set
{I,
...
, k} and whose
edges
are
the pairs
rs
for
which, either there exist
i
'"
j E Wr n Ws such that
Gij
'"
0, or there exists
i E Wr n Ws such that c
T
8(
{i})
'"
0,
is connected.
(iii) The inequality
LiEwr(Gi,n+I
+
LjEV..,\Wr
Gij)Xi,n+I
+
Li<ili,jEW
r
CijXij
::; a
defines a facet
of
CUTWrl+I' for
each
r 1,
...
, k.
Then, the inequality c
T
x
::;
a defines a facet
of
CUT~+I'
I
For example, Corollary 26.6.2
permits
to derive
that
the
pentagonal inequal-
ity:
Q(I,
1, 1,
-1,
_I)T
x
::;
0
defines a facet of CUT5, from
the
fact
that
the
triangle inequalities define facets
of CUT4. Indeed, consider
the
subsets
WI
:=
{I,
2,
4}, W
2
:=
{I,
3,
4}
and
W3
{2,3,4}
of
{I,2,3,4}.
Then,
the
inequalities from Corollary 26.6.2 (iii)
are, respectively,
the
triangle inequalities:
XI2
-
XI4
-
X24
::; 0,
XI3
-
X14
-
X34
::;
0
and
X23
X24
X34::;
o.
More generally, Corollary 26.6.2
permits
to
derive
that
any
pure
hypermetric inequality:
Q(I,
...
, 1,
-1,
...
,
_I)T
x::; 0 is facet defining
from
the
fact
that
triangle inequalities are facet defining.
A slight modification of Proposition 26.6.1 yields
the
following construction
for facets of
the
correlation polytope. Given a E R
V
"
UE"
and
a E
R,
suppose
that
the
inequality aTp
:=
Ll<i<j<n
UijPij
::; a defines a facet of
COR~.
Consider
fJ
E R
and
two elements i* E
Vn
and
j*
'I-
V
n
;
set
V
n
+1
Vn
U
{j*}
and
define
the
vector b E RV..,+l
UE,,+l
by
(26.6.3)
=
ai,i*
=
fJ,
if
i,j
E V
n
,
ifi
E
Vn
\
{i*},
We say
that
the
inequality b
T
p
::;
a is obtained from
the
inequality aT p
::;
a by
duplicating the node
i*
as the node
j*.
Note
that
this operation can
be
seen as a
special case
of
lifting.
The
next result indicates
what
value of
fJ
should
be
taken
in order
to
ensure
that
b
T
p
::;
a defines a facet
of
CO~+
I'
Proposition
26.6.4.
Suppose that the inequality
aT
p
::;
a defines a facet
of
CO~
and let
bE
RVn+lUE,,+l
be
defined
by
(26.6.3). Then the inequality b
T
p
::;
a
defines a facet
of
CO~'H
if
and only
if
fJ=a
max
(a
T
1r(SU{i*})+
L
Uii')'
s~v,,\{i'}
iESU{i'}
,
Proof. Let
fJo
denote
the
right
hand
side
in
the
relation defining
fJ.
We first
check
that
b
T
p
::;
a is valid for
COR~+I
if
and
only
if
fJ
::;
fJo.
Indeed, let T
be
a
26.6 Facets
by
Projection
419
subset
of
V
n
+1.
If
j*
if.
T,
or
if
j*
E T
and
i*
if.
T,
then
b
T
-rr(T)
= aT
-rr(T)
::;:
a,
by
construction
of
b.
If
i*,
j*
E T then, setting S
:=
T \ {i*,
j*},
we
have
b
T
-rr(T)
= aT
-rr(S
U {i*}) + L
ai,i"
+
f3.
iESU{i"}
Hence, b
T
-rr(T)
::;:
a holds for all T
~
V
n
+
1
if
and
only
if
f3
::;:
f3o.
If
f3
<
f3o,
then
every
root
of
b
T
P = a satisfies
the
equation
Pi"
,j"
=
0;
this
shows
that
b
T
P
::;:
a does not define a facet of
COR~+l.
Suppose now
that
f3
=
f3o.
We
show
that
b
T
P
::;:
a defines a facet
of
COR~+1.
For this, let (b')T P
::;:
a'
be
another
inequality such
that
{p E
CO~+l
I b
T
P = a}
~
{p E
COR~+l
I
(b'f
P =
a'l·
By
the
argument
of
Proposition
26.6.1, there exists a scalar A such
that
a'
= Aa,
bi
j
=
Abij
for all
i,j
E V
n
+1 except maybe for
the
pair
i*,j*.
As
f3
=
f3o,
we
can
find a
root
-rr(T)
of bTp = a such
that
i*,j*
E
T.
As (b'f-rr(T) =
a',
we
deduce
that
(b')i"
,j"
=
Ab
i
" ,j".
This
shows b
'
=
Ab.
I
For instance,
the
inequality:
pi"
,i"
+
Pii
-
Pi,i"
::;:
1
defines a facet of
COR~.
Applying
Proposition
26.6.4,
we
obtain
that
the
in-
equality:
Pi"
,i"
+
Pii
+ Pj,j" -
Pi,i"
-
Pi,j"
-
Pi"
,j"
::;:
1
defines a facet of
COR~.
(Note
that
these two inequalities correspond to triangle
inequalities for
the
cut
polytope; recall Figure 5.2.6.)
We
leave it to
the
reader
to
reformulate
Proposition
26.6.4 for the
cut
polytope. See Section 30.4 for
an
application of
Proposition
26.6.4
to
the parachute facet.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_27, © Springer-Verlag Berlin Heidelberg 2010
Chapter
27.
Triangle
Inequalities
As
we
will see
throughout
Part
V,
the
cut
polytope
CUT~
has
many
different
types
of
facets, most
of
them
having a
rather
complicated
structure.
Among
them,
the
most simple ones are
the
triangle facets, i.e., those defined by
the
following triangle inequalities:
(27.0.1)
Xij
-
xik
-
Xjk
::; 0,
(27.0.2)
Xij
+
xik
+
Xjk
::; 2,
for
distinct
i,j,
k E V
n
.
The
inequality (27.0.1) is a homogeneous triangle in-
equality, while (27.0.2) is nonhomogeneous.
The
homogeneous triangle inequali-
ties have already
been
considered
in
previous chapters. Note
that
(27.0.2) arises
from (27.0.1) by switching, e.g., by
the
cut
b(
{i}); hence,
the
class
of
triangle
inequalities is closed
under
switching.
The
cone
in
JRE
n
defined by
the
homo-
geneous triangle inequalities is
the
semimetric cone
MET
n,
already considered
earlier.
The
polytope
in
JRE
n
defined by all triangle inequalities (27.0.1)
and
(27.0.2) is
the
semimetric polytope
and
is denoted by
MET~.
Hence,
The
terminology used for
the
polyhedra
METn
and
MET~
comes,
of
course,
from
the
fact
that
the
distances on
Vn
that
satisfy
the
homogeneous triangle
inequalities are precisely
the
semimetrics.
Clearly,
the
semimetric polytope
MET~
is preserved by
permutation
and
switching (as
the
class
of
triangle inequalities
is
closed
under
switching), a prop-
erty
also enjoyed by
the
cut
polytope
CUT~.
In
fact, as shown
in
Laurent
[1996c],
both
polytopes
MET~
and
CUT~
have
the
same group of symmetries;
that
is,
Is(MET~)
=
Is(CUT~).
The
group
Is(CUT~)
has
been
described
in
Section 26.3.3.
Every triangle inequality defines a facet
of
the
cut
polytope. To see it, it
suffices (in view
of
the
results
of
the
preceding section on
permutation,
switching
and
O-lifting)
to
show
that
the
inequality:
422
Chapter
27. Triangle Inequalities
defines a facet
of
CUT
a
.
This
is indeed
the
case as
the
cut
vectors 8( {1})
and
8({2}) are two
(=
@
-1)
linearly
independent
roots
of
this
inequality. Hence,
there
are
3(~)
triangle
facets for
CUTn
and
4(~)
triangle facets for
CUT~.
The
triangle
inequalities are sufficient for describing
the
cut
polyhedra
for
n
~
4,
i.e.,
CUTn
=
METn
and
CUT~
=
MET~
for n =
3,4,
but
CUTn
C
MET
n
,
CUT~
C
MET~
for n
:2:
5.
To see it, observe
that
the
vector
(~,
...
,
~)
E
~En
belongs
to
MET~
but
not
to
CUT~
if
n
:2:
5.
Alternatively,
the
pentagonal
inequality (6.1.9) defines a (nontriangle) facet
of
the
cut
polytope
on
:2:
5 elements.
In
some sense,
K5
is
the
unique
"minimal
obstruction"
for
the
following
property:
The
triangle inequalities form a linear description
of
the
cut
polytope.
Indeed,
the
triangle inequalities (in fact,
their
projections) form
the
whole linear description
of
the
cut
polytope
of
a
graph
G if
and
only
if
G
has
no
K5-minor; see
Theorem
27.3.6.
Every
cut
vector is a vertex
of
the
semimetric polytope; moreover,
the
cut
vectors are
the
only integral vectors
ofMET~
(see
Proposition
27.2.1). However,
for
n
:2:
5,
MET~
has
lots
of
additional
vertices, all
of
them
having some fractional
component.
Hence, a linear description
of
CUT~
arises from
that
of
MET~
by
adding
constraints
that
cut
off these fractional vertices.
The
vertices
of
MET~
are
studied,
in
particular,
in
Laurent
[1996c]
and
Laurent
and
Poljak
[1992].
On
the
other
hand,
the
semimetric cone
METn
contains integral
points
that
are
not
cut
vectors. Indeed, given any
partition
(SI, .
..
, Sk)
of
V
n
,
the
multicut
vector 8(SI,
..
. , Sk)
is
a (0, I)-valued
member
of
METn.
On
the
other
hand,
it
is
easy
to
check
that
the
only integral
points
of
MET
n are
the
multicut
semimetrics.
Note
that
1
8(SI,
...
, Sk) = - L 8(Sh).
21:<::h9
Therefore,
the
only integral
points
of
MET
n
that
lie
on
an
extreme
ray
of
MET
n
are
the
usual
cut
vectors 8(S) for S
~
V
n
.
The
extreme
rays
of
METn
have
been
studied,
in
particular,
in
Avis [1977, 1980a, 1980b], Lomonosov [1978, 1985]'
Howe,
Johnson
and
Lawrence [1986]' Grishukhin [1992a].
The
order
of
magnitude
of
the
number
of
extreme
rays
of
METn
is known; Avis [1980b] gives a lower
bound
in
2n2/2-0(n3/2)
and
Graham,
Yao
and
Yao
[1980]
prove
the
upper
bound
22.72n2.
One
of
the
important
motivations for
the
study
of
the
semimetric cone
comes from
its
role
in
the
feasibility problem for
multicommodity
flows (Iri [1971];
see also Lomonosov [1985], Avis
and
Deza [1991]).
Although
the
triangle
facets represent,
in
general, only a tiny fraction
of
all
the
facets
of
the
cut
polytope,
they
seem
to
play nevertheless
an
important
role.
This
is
indicated
by
their
many geometric properties. We now discuss several
properties
and
features
of
the
triangle inequalities.
Further
geometric
properties
will be described
in
Chapter
31.
27.1 Triangle Inequalities for
the
Correlation
Polytope
423
27.1
Triangle
Inequalities
for
the
Correlation
Poly-
tope
Let us recall how
the
triangle inequalities look like, when formulated
in
the
context
of
the
correlation polyhedra. Let us call these reformulated inequalities
the
correlation triangle inequalities.
This
information has already been given in
Figure
5.2.6;
we
reproduce
part
of
it
here, for convenience. (We
remind
that
the
inequalities
on
the
"cut side" are defined
in
the
space ffi.En+l while
the
inequalities
on
the
"correlation side" live
in
the
space ffi.v
n
UE
n
.)
"cut
side" "correlation side"
dE
ffi.En+l
P E ffi.VnUE
n
8(S) ( for S
~
V
n
)
'/f(S)
CUT
n
+
1
COR,..
CUT~+1
COR~
(Rooted) triangle (Rooted) correlation triangle
inequalities: inequalities:
d(i,j)
-
d(i,n+
1) -
d(j,n+
1)
~
0
o
~
Pij
d(i, n + 1) - d(j, n + 1) -
d(i,j)
~
0
Pij
~
Pii
d(j, n + 1) - d(i, n + 1) -
d(i,j)
~
0
Pij
~
Pjj
d(i, n + 1) + d(j, n + 1) +
d(i,j)
~
2
Pii
+
Pjj
-
Pij
~
1
(i,j
E V
n
)
(Unrooted) triangle (Unrooted) correlation triangle
inequalities: inequalities:
d(i,j)
- d(i, k) - d(j,
k)
~
0
-Pkk
-
Pij
+
Pik
+
Pjk
~
0
d(i,j)
+ d(i, k) + d(j,
k)
~
2
Pii
+
Pjj
+
Pkk
-
Pij
-
Pik
-
Pjk
~
1
(i,j,
k E V
n
)
Figure
27.1.1: Triangle inequalities for
cut
and
correlation
polyhedra
The
rooted
triangle inequalities are those
that
use
the
element n +
1;
they
will
be
considered
in
detail
in
the
next subsection.
The
correlation triangle inequalities have a nice
interpretation
in
terms
of
probabilities. Indeed, recall from
Proposition
5.3.4
that
every vector P E
COR~
represents
the
joint
correlations
/t(AinAj)
(1
~
i
~
j
~
n)
ofn
events
AI"'"
An
in
some probability space.
Then,
the
rooted correlation triangle inequalities
simply
express
the
following basic properties:
•
The
joint
probability
/t(Ai
n
Aj)
of
two events is nonnegative
and
less
than
or
424
Chapter
27. Triangle
Inequalities
equal
to
the
probability
of
each
of
the
two events,
and
•
the
probability
jL(Ai U
Aj)
(=
jL(Ai) + jL(Aj) - jL(Ai n
Aj))
of
their
union
is
less
than
or
equal
to
1.
The
unrooted
inequalities
can
be expressed as follows:
•
-jL(Ak)
- jL(Ai n
Aj)
+ jL(Ai n A
k
) + jL(Aj n A
k
) =
-jL(A
k
) - jL(Ai
n
Aj)
+
jL(Ak n
(Ai
U
Aj))
+ jL(Ak n
Ai
n
Aj),
which is
clearly::;
0,
and
• jL(Ai) +
jL(Aj)
+ jL(Ak) - jL(Ai n
Aj)
- jL(Ai n A
k
) - jL(Aj n A
k
)
= jL(Ai U
Aj
U
A
k
) - jL(Ai n
Aj
n A
k
), which is
clearly::;
1.
This
shows
again
the
validity
of
the
correlation
triangle
inequalities for
COR~.
There
is
another
natural
way
of
generating
the
rooted
correlation
triangle
inequalities.
Remember
that
the
polytope
CO~
can
be
expressed as
Hence, valid inequalities for
COR~
can
be
generated
in
the
following way. Sup-
pose
that
aT
x
2':
a
and
b
T
x
2':
{3
hold
for each x E {O,l}n.
Then,
the
inequality
also
holds
for each x E
{o,l}n.
If
we
develop
the
quantity
(aTx
- a)
(bTx
-
(3)
and
linearize, i.e.,
if
we
replace each XiXj
(i
i=-
j)
by
the
variable Pij
and
each
XiXi
by
the
variable
Pii,
then
we
obtain
an
inequality
which is clearly valid for
COR~.
We
illustrate
the
method,
starting
from
the
inequalities:
Xi
2':
0,
1 -
Xi
2':
0, Xj
2':
0, 1 - Xj
2':
°
which
hold
trivially
for x E
{O,
l}n.
By
multiplying
them
pairwise,
we
obtain
the
inequalities:
XiXj
2':
0, i.e.,
xi(l
- Xj)
2':
0, i.e.,
xj(l
- Xi)
2':
0, i.e.,
(1
-
xi)(l
- Xj)
2':
0,
i.e.,
Pij
2':
0,
Pii
2':
Pij,
Pjj
2':
Pij,
Pii
+
Pjj
- Pij
::;
1.
So,
we
have
generated
the
rooted
correlation
triangle
inequalities.
This
method
is,
in
fact,
described
in
Lovasz
and
Schrijver
[1991]
and
Balas,
Ceria
and
Cor-
nuejols [1993] as a way
of
generating
a
tighter
relaxation
from a given
linear
relaxation
of
a Ol-polytope.
27.2
Rooted
Triangle
Inequalities
In
this
section,
we
consider
the
triangle
inequalities for
the
polytope
CUT~+l;
hence,
they
are defined
on
the
n + 1
elements
of
the
set
Vn+l
=
{I,
...
,
n,
n +
I}.
27.2 Rooted Triangle Inequalities
425
Then,
a triangle inequality is called a rooted triangle inequality if
it
uses
the
element n + 1, Le.,
if
it
is of
the
form:
Xij
Xik
Xjk
$ 0 or
Xi)
+
Xik
+
Xjk
$
2,
for some
i,j,
k E V
n
+
1
such
that
n + 1 E
{i,j,
k}.
The
rooted triangle inequalities define a polytope, called
the
rooted semimet-
ric polytope,
and
denoted by
RMET~+l'
Therefore,
CVT~+l
<;;;
MET~+l
<;;;
Although
the
rooted polytope
RMET~+
1
is
a weaker relaxation of
CUT~+l
than
MET~+l'
it
contains already a lot of information. In particular, as
stated
in
Proposition
27.2.1 below,
it
constitutes an integer programming formulation for
the
cut
polytope.
In
fact,
the
rooted semimetric polytope has some nice properties,
that
the
usual semimetric polytope does not have. For instance,
Padberg
[19891
shows
that
every vertex of
RMET~+l
is half-integral,
Le.,
has components 0,
1,~.
In
contrast,
MET~+l
has very complicated vertices, with arbitrarily large denomi-
nator.
In
fact,
the
unrooted triangle inequalities are already sufficient for
cutting
off
the
fractional vertices of
RMET~+l'
as no vertex of
MET~+l
is half-integraL
We present below several properties of
the
rooted semimetric polytope. Some
of
them
will
be
given for convenience in
the
context of correlations;
that
is, for
~(RMET~+l)'
the
polytope defined by
the
rooted
correlation triangle inequalities
(see Figure 27.1.1).
27.2.1
An
Integer
Programming
Formulation
for
Max-Cut
Proposition
27.2.1. The only integral vectors
of
RMET~
are
the cut vectors
8 (S) for S
Vn
. Moreover, every cut vector is a vertex
of
RMET~.
Proof. Let X E
RMET~
n
{O,
1 }En. Set I
:=
{i E
Vn
,
Xi,n+l
=
O}
and
.1
{i E
Vn
I
Xi,n+l
I}. As x satisfies
the
rooted triangle inequalities,
we
obtain
that
Xij
0 for all i
i=
j such
that
i,j
E I or i, j E
.1,
and
Xij
= 1 for all
i E
I,
j E
.1.
This
shows
that
x is equal
to
the
cut
vector 8(.1). We now show
that
every
cut
vector is a vertex
of
RMET~.
In
view of
the
symmetry
properties
of
RMET~,
it
suffices
to
show
that
the
origin is a vertex
of
RMET~.
This
follows from
the
fact
that
the
homogeneous rooted triangle inequalities (which
all contain
the
origin) have full
rank
(~).
I
Hence,
the
system which consists of
the
rooted triangle inequalities together
with
the
integrality constraint:
Xij
0,
1 for all
ij
forms
an
integer programming formulation for
the
max-cut problem.
In
other
words, given a weight function c ,
the
max-cut problem:
426
Chapter
27.
Triangle Inequalities
can
be reformulated as the problem:
max
x E
RMET;+l
x E {O,l}En+l.
Hence, if one wishes to solve
the
max-cut problem using linear programming
techniques, one faces
the
problem of finding what are
the
additional constraints
needed to be added to the above formulation
in
order
to
eliminate
the
integrality
condition.
This
is
the
question of finding the facet defining inequalities for
the
cut polytope, which forms
the
main topic of
Part
V.
27.2.2
Volume
of
the
Rooted
Semimetric
Polytope
Computing
the
exact volume of a polytope is,
in
general, a difficult problem.
A nice property of the rooted triangle inequalities is
that
one
can
compute ex-
actly
the
volume of
the
rooted semimetric polytope. This was done by Ko, Lee
and
Steingrimsson
[1997]
who showed, using the switching symmetries, how
the
problem
can
be
reduced to
that
of computing
the
volume of
an
order polytope.
Theorem 27.2.2.
Set
d
:=
(nil). Then, the d-dimensional volume
of
the rooted
semimetric
polytope
RMET;+l
is equal to
o
n!
n
vol RMETn+l = (2n)!2
The d-dimensional volume
of
its image
under
the covariance mapping is
vol
e(RMET;+I)
=
(nl),2
2n
-
d
.
2n.
Proof. To simplify the notation, set Qn
:=
e(RMET;+1)'
In
a first step, let us
compute
the
d-dimensional volume of Qn.
The
polytope Qn is defined by the
rooted
triangle inequalities, namely,
(i)
Pij
~
0,
Pij
~
Pii,
Pij
~
Pjj,
(ii)
Pii
+
Pjj
~
1 +
Pij
for all 1
~
i < j
~
n. For a E
{O,
I}
n,
set
G
a
:=
{p
E Qn I ai
~Pii
~
a.;
+
~
(i 1,
...
,n)}.
Then,
for distinct
a,
b E
{O,
l}n,
the d-dimensional volume of G
a
n
Gb
is equal
to
o (as G
n
n
Gb
has dimension < d). Clearly, Qn is the union
of
the polytopes G
n
(for a E
{O,l}n).
Hence,
vol
Qn L vol
Ga.
aE{O,l }n