Deza M.M., Laurent M. Geometry of Cuts and Metrics

28.4

Gap

Inequalities

457

Then,

d satisfies all

the

negative

type

inequalities

if

and

only if

the

matrix

(Pij)

is positive semidefinite. Moreover, a negative type inequality violated by d (if

some exists)

can

be found in polynomial

time

(by

Proposition

2.4.3). I

28.4

Gap

Inequalities

We describe here a large class of valid inequalities for

CUT~,

which generalizes

the

hypermetric

and

negative

type

inequalities.

It

was

introduced

by

Laurent

and

Poljak

[1996b]. For

bE

zn,

the

quantity

feb)

:=

min

Ib(S) -

b(S)1

S<;;Vn

is

called

the

gap

of

b.

(Here, S

:=

Vn

\ S.) We also set

Then,

the

inequality:

(28.4.1)

a(b):=

L b

i

.

l::>i::>n

is

called a

gap

inequality.

The

of

the

gap

inequal-

ities

and

invariance

of

the

gap

under

switching.

Lemma

28.4.2.

Every

gap

inequality (28.4.1) is valid for

CUT~.

Proof. Let S

~

Vn

and

suppose, e.g.,

that

b(S)

::;

~.

Then,

by

the

definition

of

the

gap

feb),

we

have

that

b(S)

::;

<7(b)~'Y(b),

which implies

that

Q(bf

O(S) =

b(S)(a(b) - b(S))

::;

<7(bj2~'Y(b)2.

I

Lemma

28.4.3.

Let b E

zn,

let A

~

Vn

and let

b'

be

obtained from b

by

chang-

ing the signs

of

its components indexed

by

A,

i.e., b::=

-bi

ifi

E A and b::= b

i

if

i E

Vn

\

A.

Then, f(b') = feb).

Proof.

For S

~

V

n

,

we

have b'(SL'-.A) = b(S \ A) - b(A \

S)

= b(S) - b(A)

and

b'(SL'-.A) =

b(SnA)

-

b(SnA)

= b(S)

-b(A).

This

implies

that

f(b') = feb). I

Clearly,

the

class of inequalities (28.4.1) is closed

under

permutation.

Lemma

28.4.3 implies

that

it

is also closed

under

switching, since

if

b'

is

obtained

from b by changing

the

signs

of

its

components indexed by

the

set A

~

V

n

.

Therefore,

the

class of gap inequalities is closed

under

permutation

and

switching.

458

Chapter

28.

Hypermetric Inequalities

Observe

that

,(b)

and

a(b) have

the

same parity. Trivially,

,(b)

:S

a(b). One

can

check

that

,(b):S

ml1xlb;l.

•

In

particular,

,(b)

= 1 if a(b) =

1,

and

,(b)

= 0 if a(b) =

O.

Therefore,

the

gap inequalities (28.4.1) with a(b) = 1 are precisely

the

hypermetric inequalities,

while those with

a(b) = 0 are

the

negative type inequalities. Using

Lemma

28.4.3

we

can

identify which gap inequalities arise as switchings

of

hypermetric

or

neg-

ative type inequalities.

Lemma

28.4.4.

Let

b E

zn.

Then, the inequality (28.4.1) can

be

obtained by

switching

from

a hypermetric inequality (resp. from a negative type inequality)

if

and

only

if

,(b)

= 1 (resp.

,(b)

=

0)

or, equivalently,

if

there exists a subset

S

~

Vn

such that

b(S)

=

~(a(b)

-

1)

(resp.

b(S)

=

~a(b)).

I

Hence,

the

orbits

of

faces

of

CUT~

defined by hypermetric inequalities consist

of

those faces

of

CUT~

defined by inequalities

of

type (28.4.1) for which

,(b)

= 1

holds.

In

other

words,

Chapter

28

is

devoted to

the

class

of

the

gap inequalities

(28.4.1) with

,(b)

= 1.

We

remind

that

no inequality (28.4.1) with gap

,(b)

= 0

is

facet defining

(by Corollary 6.1.4).

In

the

case

of

a gap

,(b)

= 1, large classes

of

inequalities

(28.4.1) defining facets have been presented in Section 28.2.

The

gap inequalities

(28.4.1) seem difficult to study,

in

the

case

of

a gap

,(b)

2

2.

In

particular,

we

do

not

know any example

of

an

integer sequence b E

zn

with

,(b)

2 2

and

for

which

the

gap inequality (28.4.1) defines a facet

of

CUT~.

Thus,

the

following

problem

is open.

Problem

28.4.5.

Does there exist an integer sequence b with gap

,(b)

2 2

for

which the gap inequality: Q(b)T x

:S

!(a

2

(b) -

,2(b))

defines a facet

of

the

cut

polytope?

Only

the

following

is

known. Laurent

and

Poljak

[1996b]

show

2

that,

if

the

components

of

b take only two distinct values (in absolute value)

and

if

,(b)

2

2,

then

the

gap

inequality (28.4.1)

is

not facet inducing.

In

addition,

the

gap inequalities present the following difficulty:

It

is

an

NP-

hard

problem

to

compute

the gap

of

a sequence b E

zn

and, thus, to

compute

the

exact

right-hand

side

of

the

inequality (28.4.1). Indeed, given b E

zn,

deciding

whether

,(b)

= 0

amounts

to deciding whether b can

be

partitioned

into two

subsequences

of

equal sums; this

is

the

partition

problem, which

is

known to be

NP-complete (Garey

and

Johnson

[1979]).

In

order to avoid this difficulty, one may consider

the

following weaker in-

equality:

2Laurent

and

Poljak

[1996bJ also

present

a

characterization

of

the

sequences b for which

(28.4.1) is

facet

defining

that

involves

only

conditions expressed in

the

n-dimensional

space

instead

of

the

dimension

(~)

in

which

the

cut

polytope

CUT~

lives.

28.4 Gap Inequalities

459

(28.4.6)

instead

of

(28.4.1).

The

inequality (28.4.6) is trivially valid for

CUT~.

However,

no

inequality (28.4.6) defines a facet

of

CUT~.

(Indeed,

if

,),(b)

i=

0

then

(28.4.6)

contains no root

at

all and,

if

')'(b)

0,

then

(28.4.6)

is

a switching

of

a negative

type

inequality.)

The

inequalities (28.4.6) have nevertheless a number of interesting properties.

As

we

see below they present, in particular, the big advantage of being much

more tractable

than

the

gap inequalities (28.4.1).

28.4.1

A

Positive

Semidefinite

Relaxation

for

Max-Cut

Let

.:In

denote the set in

JRE

n

which

is

defined by the inequalities (28.4.6) for all

bE

zn,

Le.,

Then,

.:In

is

a convex body in

JRE

n

.

A first interesting property is

that

the sepa-

ration problem over

.:In

can

be

solved in polynomial time. This is

the

following

problem:

Given a vector x E

~n,

determine whether x belongs to

.:In.

If

not,

find b

E

zn

such that Q(b)T

x>

!0"(b)2.

This problem can solved in

the

following

way:

For x E

JREn

define the n x n

symmetric matrix X with zero diagonal

and

with

ij-th

off-diagonal entry

Xij'

Then,

x E

.:In'';=:;'

the

matrix

J -

2X

is positive semidefinite,

where

J denotes

the

all-ones matrix. (This follows from the fact

that

b

T

(J

2X)b

0"(b)2

- 4Q(b)T x for all b E

JRn.)

The

result

now

follows in view of

Proposition 2.4.3.

Therefore, one can optimize any linear objective function over

.:In

in polyno-

mial time.

That

is, given c E

~n,

one can compute the quantity:

B(c)

:=

max(c

T

x I x E

.:In)

in polynomial time (with an arbitrary precision); see Goemans

and

Williamson

[1994]

for more details.

As

the inequalities (28.4.6) are valid for

the

cut polytope

CUT~,

the convex body.:ln provides a relaxation

of

CUT~,

i.e.,

460

Chapter

28.

Hypermetric

Inequalities

Therefore,

the

quantity

B(c)

is

an

upper

bound

3

for

the

value of

the

max-cut

problem:

mc(Kn,

c)

:=

max(c

T

x 1 x E

CUT~).

That

is,

mc(Kn,

c)

:::;

B(c)

for all c E

~n.

Goemans

and

Williamson

[1994]

show

that

the

quantity

B(c)

provides a very

good

approximation

for

the

max-cut

mc(Kn,

c),

when

the

weight

function

c is nonnegative. Namely,

Theorem

28.4.1.

Given c E

~n,

we

have

mc(Kn,

c)

---'---'-'--'-

2:

0:

B(c)

h

.

2 0

were

0:

:=

O~}l!!1T

'If

1 _ cos

o·

.87856 <

0:

<

.8i857.

The quantity

0:

can

be

estimated

as

follows:

Proof. As above, for a vector x E

REn

we

let X denote

the

n x n

symmetric

matrix

with

zero diagonal

and

with

off-diagonal entries Xij. Set Y

:=

J -

2X.

Then,

x E In

~

Y

~

o.

Hence,

the

quantity

B(c)

can

be

reformulated

as

B(c)

=

max

~

L cij(1 - Yij)

I~i<j~n

s.t. Y = (Yij)

~

0

Yii

= 1 (i = 1,

...

, n).

Using

the

representation

of

positive semidefinite

matrices

as

Gram

matrices,

we

can

further

rewrite

B(c)

as

(28.4.8)

B(c)

=

max

~

L cij(1 -

v[

Vj)

I~i<j~n

s.t.

VI,

...

,V

n

E

S,

where S

:=

{x

E R

n

:11

x

112=

I}.

Let

VI,

...

,V

n

E R

n

be

unit

vectors realizing

the

optimum

in

the

above

program,

i.e.,

B(c)

=

~

L cij(1 -

v[

Vj).

The

I~i<j~n

crucial

step

in

the

proof

consists now

of

constructing

a

'good'

random

cut,

i.e.,

whose weight is

not

too

far from

the

value

of

the

max-cut.

For this, one proceeds

as follows:

3In

fact,

this

upper

bound

coincides

with

another

upper

bound

cp(c)

introduced

earlier

by

Delorme

and

Poljak

[1993a]

and

defined

in

terms

of

a

minimization

problem

involving

the

maximum

eigenvalue

of

the

associated

Laplacian

matrix

L(c).

Namely,

L(c) is

the

symmetric

n x n

matrix

with

diagonal

entries

c

T

8(i) (for i = 1,

...

,

n)

and

with

off-diagonal

entries

-C;j

(for i

-#

j).

That

the

two

bounds

cp(c)

and

B(c) coincide

has

been

shown

by

Poljak

and

Rendl

[1995]

using

duality

of

semidefinite

programming.

28.4

Gap

Inequalities

• Select a

random

unit

vector r E

lPl.

n

.

• Set S

:=

{i

E

Vn

I

v;

r

2:

O}.

Let

E(c

T

8(S))

denote

the

expected weight

of

the

cut

vector 8(S).

Then,

E(c

T

8(S))

:S

mc(Kn,c).

We now evaluate a lower

bound

for

E(c

T

8(S)). We have

E(c

T

8(S)) = L

CijPij,

l~i<j~n

461

where

Pij

is

the

probability

that

an

edge

ij

of

Kn

is

cut

by

the

partition

(S,

Vn

\S).

This

probability

is equal

to

the

probability4

that

a

random

hyperplane

separates

the

two vectors

Vi

and

Vj.

Hence,

Therefore,

1 T

Pij

= - arccos(vi

Vj).

7r

L

arccos(v;

Vj)

L 1 -

v;

Vj

B(

)

c··

> a

c··

= a c

..

'J

7r -

..

'J

2 '

l~'<J~n

where

the

last

inequality follows by

the

definition

of

a.

This

shows

the

desired

inequality:

aB(c)

:Smc(Kn,c).

I

The

above

proof

shows

the

existence

of

a

random

cut

whose weight is

at

least

a

times

the

optimum

mc(Kn,

c).

Goemans

and

Williamson

[1994]

show

that

the

above

procedure

can

be

derandomized so as

to

yield a polynomial

deterministic

(a

- E)-approximation algorithm for

the

max-cut

problem (for any E > 0). Note

that

the

best

previous result

in

this

direction was a

!-approximation

algorithm,

due

to

Sahni

and

Gonzales [1976].

Goemans

and

Williamson's result came as a

breakthrough

in

the

area

of

combinatorial

optimization.

It

shows, indeed, how semidefinite

programming

can

be

applied

successfully for designing

approximation

algorithms for combinatorial

problems.

The

method

has

been

since

then

applied

to

several

other

problems;

see,

in

particular,

Goemans

and

Williamson [1994], Karger, Motwani

and

Sudan

[1994]' Frieze

and

Jerrum

[1995].

Consider

the

following instance of

the

max-cut

problem: n = 5

and

the

weight function c takes value 1

on

the

edges of

the

5-circuit C

5

and

value 0

elsewhere.

Then,

mc(K

5

,c)

= 4

and

B(c)

=

~(1

+ cos(K)) = 25+;15

(obtained

by

taking

in

(28.4.8)

the

vectors

Vi

=

(cos(4~"'),sin(4~"'))

for i =

1,

...

,5; see

Delorme

and

Poljak [1993b]). Hence,

mcftcr

1

=

251~y'5

(=

.88445). Delorme

and

Poljak [1993b] conjecture

that

this

is

the

worst case ratio, i.e.,

that

mc(Kn,c)

> 32

(=.88445)

B(c)

-

25

+

5V5

'This

probability

has

been,

in

fact,

computed

in

Section

6.4;

by

relation(6.4.4),

it

is

equal

to

arccos(

vT

Vj)

/

7r.

462

Chapter

28.

Hypermetric

Inequalities

for all c

2:

O.

Hence,

the

result

from

Theorem

28.4.7 shows a lower

bound,

which

is very close

to

this

conjectured value.

Karloff [1996]

has

made

recently a detailed analysis

of

the

performance

of

the

Goemans-

Williamson

algorithm.

We

remind

the

inequalities:

(28.4.9)

a

< E(c

T

6(5)) < mc(Kn,c) < 1

- B(c) - B(c)

-,

where

E(c

T

6(5)) is

the

expected

weight

of

a

cut

constructed

by

the

random

procedure

described

in

the

proof

of

Theorem

28.4.7. Karloff

constructs

a class

of

instances

(Kn' c) for which

equality

is

attained

in

the

right

most

inequality

of

(28.4.9)

and

also

(asymptotically)

in

the

left

most

inequality

of

(28.4.9). (Namely,

given

an

even integer m

and

b S

TI'

consider

the

graph

J(m,

m/2,

b)

whose

node

set

is

the

family A

of

subsets

of

[1,

m]

of

cardinality

m/2,

with

an

edge

between

A,

B E A

if

IA n BI =

b.

Now, define a weight function c

on

the

edges

of

Kn

(n

:=

IAI)

by

taking

value 1

on

the

edges

of

J(m,

m/2,

b)

and

value 0 elsewhere.)

The

convex set underlying

the

computation

of

the

bound

B(c) is

the

set

:Tn

or,

rather,

its image

En

under

the

linear bijection: x

1---+

1 - 2x.

That

is,

En

:=

{Y

n X n

symmetric

I Y

~

0,

Yii

= 1 for i = 1,

...

,

n}.

The

set

En

is called

an

elliptope

(standing

for ellipsoid

and

polytope) in

Laurent

and

Poljak

[1995b]. Hence,

En

can

be

seen as

the

intersection

of

the

positive

semidefinite cone

PSD

n

by

the

hyperplanes

Yii

= 1 (i = 1,

...

,n).

The

elliptope

E3

(or

rather

its 3-dimensional

projection

consisting

of

the

upper

triangular

parts

of

the

matrices)

is shown in

Figure

31.3.6.

The

elliptope

En

has

been

studied

in

detail

by

Laurent

and

Poljak

[1995b,

1996a].

For

instance, all

the

possible dimensions for

the

faces

of

En

are

known

as well as for

its

polyhedral

faces (see Section 31.5);

it

is shown in

Laurent

and

Poljak

[1995b]

that

En

has vertices

(that

is,

extreme

points

with

full-dimensional

normal

cone)

that

are

precisely

the

'cut

matrices'

xx

T

for x E

{-I,

l}n. More-

over,

the

link

with

the

well-known

theta

function

introduced

by

Lovasz

[1979]

for

approximating

the

Shannon

capacity

and

the

stability

number

of

a

graph

is

described

in

Laurent,

Poljak

and

Rendl

[1997].

The

elliptope

En

is also relevant

to

the

following

problem,

known in linear

algebra

as

the

positive semidefinite completion problem

5

:

Given a partial real

symmetric

matrix

X whose entries are only spec-

ified on a subset F

of

the positions (including all diagonal positions),

determine whether the missing entries can

be

completed so

as

to make

X positive semidefinite.

An

easy observation is

that

it

suffices

to

consider

the

positive semidefinite com-

pletion

problem

for

matrices

whose diagonal entries

are

all

equal

to

1.

(Indeed,

'We

refer

to

Johnson

[1990] for a

comprehensive

survey

on

completion

problems.

28.5

Additional

Notes

463

if

a

partial

symmetric

matrix

X is

com

pie

table

to

a positive semidefinite

matrix,

then

its

diagonal

entries are nonnegative. Moreover, we

can

suppose

that

all di-

agonal

entries

are

positive as, otherwise,

the

problem

reduces

to

considering

the

submatrix

of

X

with

positive diagonal entries. Finally,

if

D

denotes

the

diagonal

matrix

whose

ith-diagonal

entry

is

Jx

..

,

then

the

partial

matrix

X'

:=

DX

D

(with

entries ,;xx'.'x·

..

for

ij

E F) is

com;letable

to

a positive semidefinite

matrix

11

if

and

only

if

the

same

holds for

X.

Now

X'

is a

partial

symmetric

matrix

with

an

all-ones diagonal.)

In

the

case

of

partial

symmetric

matrices

with

an

all-ones diagonal,

the

pos-

itive semidefinite

completion

problem

amounts

to

the

problem

of

deciding

mem-

bership

in

the

projection

E(G) of

the

elliptope

En

on

the

subspace

lIRE,

where

G

= (Vn'

E)

denotes

the

graph

corresponding

to

the

specified off-diagonal posi-

tions

(that

is, E

:=

F \

{ii

I i = 1,

...

, n}). A description (in closed form)

of

the

projected

elliptope

E(

G) is known for several classes of

graphs

G, e.g., for

chordal

graphs

and

for series-parallel graphs. Details are given

in

Section 31.3.

28.5

Additional

Notes

Improving

Faces

by

Subtracting

Inequalities.

We

mention

here a

general

technique,

introduced

in

De Simone, Deza

and

Laurent

[1994], for

constructing

from a given face F

another

face G containing F

and

of

higher dimension. As

an

example,

we

apply

it

to

some

hypermetric

inequalities.

Suppose

that

we

have a valid inequality v

T

x

::;

0 for

CUT

n

.

Suppose

also

that

we

can

find

another

valid inequality w

T

x

::;

0 such

that

the

inequality

(v -

wl

x::;

0

remains

valid for

CUT

n

.

Let

Fv

(resp. F

w

, F

v

-

w

)

denote

the

face

of

CUTn

defined

by

the

inequality

vTx

::;

0 (resp.

wTx

::;

0, (v -

wlx

::;

0).

Then,

Fv

=

Fw

n F

v

-

w

.

Hence,

the

dimension

of

F w ( or

of

F

v

-

w

)

is

greater

than

or

equal

to

the

dimension

of

Fv' We give

in

Theorem

28.5.2 below

an

example where

the

face F

v

-

w

is, in

fact, a facet

of

CUT

n

. We

start

with

an

easy

remark.

Lemma

28.5.1.

Let

v

T

x

::;

0

and

w

T

x

::;

0

be

two valid inequalities

for

CUTn

and

let F

v

,

Fw

denote

the faces

of

CUTn

that

they

define, respectively.

If

Fv

~

F

w

,

then

the inequality

(Mwv

-

mvwl

x

::;

0 is valid

for

CUT

n

,

where

mv

denotes

the

minimum

nonzero value

of

Iv

T

6(8) I

and

Mw

denotes

the

maxi-

mum

value

of

Iw

T

b(8)1

for

all subsets 8

of

{I,

...

n}.

I

Observe

that,

with

the

notation

of

Lemma

28.5.1,

the

face defined

by

the

inequality

(Mwv-mvw)T

x

::;

0 contains

the

face Fv. Moreover,

ifmv

2:

Mw = 2,

then

the

inequality

(v

-

w)T

X

::;

0 is also valid for

CUTn;

for example,

mv

=

Mv

= 2 for

any

triangle

facet.

Let

us look

at

an

example. Consider Q7(1,

3,

2,

-1,

-1, -1,

-2l

x

::;

0 as

v

T

x

::;

0

and

the

inequality

Q7(0,

1,

1,0,0,0,

_1)T

X

::;

0 as w

T

x

::;

O.

By

Propo-

464

Chapter

28.

Hypermetric

Inequalities

sition

28.2.1, we know

that

Fv

~

Fw'

Therefore, as mv =

Mw

= 2

and

setting

b

:=

(1,3,2,

-1,

-2)

and

d

:=

(0,1,1,0,0,0,

-1),

the

inequality:

(v - wf x = L

(b;bj

- d;dj)x;j

::;

°

19<j::;7

is valid for CUT7.

In

fact,

it

defines a facet of CUT7 (indeed,

Q7(bf

x

::;

°

has

19

linearly

independent

roots

which,

together

with

the

cut

8(

{I,

7}), form a

set

of

20

linearly

independent

roots

of

the

above inequality). (Observe

that

the

above

inequality

(v - wf x

::;

° is,

in

fact, switching equivalent

to

the

clique-web

inequality

CWi(3,

2, 2,

-1,

-If

x

::;

0, which will

be

defined

in

the

following result.

Theorem

28.5.2.

For

n

2:

7,

let b = (2n -

13,3,2,

-1,

-1, -1, -2,

...

,-2)

and

let d

= (n -

7,1,1,0,0,0,

-1,

...

,-1)

be

two

vectors in

zn.

The inequality:

~

(bb - d'd')x" < °

~

, J

'J

'J-

defines a facet

of

CUT

n

.

I

Generalization

to

Other

Cut

Families.

We now

indicate

how

hypermet-

ric inequalities

can

be

modified so as

to

yield valid inequalities for

other

cut

polyhedra.

Inequalities

for

Even

T-Cuts.

Let T

~

Vn

be

a set of even cardinality. Recall

that

8(S) is

an

even

T-cut

vector

if

S

nTis

even.

Let

b E

zn

such

that

b

i

is

odd

for all i E T

and

b;

is even for all i E

Vn

\ T

and

2:i'=1

bi

=

2.

Then,

the

inequality:

Q(bfx::;o

is valid for all even

T-cut

vectors. (Indeed, let 8(S)

be

a

cut

vector

such

that

IS

n

TI

is even.

Then,

Q(bf

8(S) = b(S)(2 - b(S))

::;

0,

since b(S) = b(S n

T)

+

b(

S -

T)

i=

1 as

b(

S)

is

an

even

number.)

In

the

special case

when

T =

Vn

and

when

Ib;1

= 1 for all i E V

n

,

then

the

above

inequality

defines a facet of

the

even

cut

cone

ECUT

n

(Deza

and

Laurent

[1993b]).

Inequalities

for

t-Ary

Cuts.

Let t

2:

2

be

an

integer

and

suppose

that

n

==

°

(mod

t).

Then,

the

cut

vector 8(S) is

said

to

be

t-ary

if

lSI

==

°

(mod

t).

Hence,

the

notions

of

2-ary

and

even

cut

vectors are the same. Let b E

zn

such

that

2:i'=1

b;

= t

and

b;

==

(J

(mod

t) for all i E V

n

,

for some

(J

E

{I,

2,

...

t - I}.

Then,

the

inequality:

Q(bf

x::; °

is valid for all

t-ary

cut

vectors. (Indeed, let 8(S)

be

a

cut

vector

such

that

lSI

==

°

(mod

t).

Then,

Q(bf8(S)

= b(S)(t - b(S))

::;

0, since b(S)

==

(JISI

==

°

(modt).)

28.5

Additional

Notes

465

Inequalities

for

Multicuts.

Let b E

;En

with

eJ

:=

L:i=l

bi

;:::

1.

Then,

the

inequality:

Q(b)T

x::::

eJ(eJ

2-

1)

is valid for

the

multicut

polytope

MC~.

Moreover, Griitschel

and

Wakabayashi

[1990]

show

that

this

inequality

defines a facet of

MC~

in

the

special case

when

Ibil

= 1 for all i E V

n

.

Other

classes of such facets

can

be

found

in

Griitschel

and

Wakabayashi

[1990]

and

Deza, Griitschel

and

Laurent

[1992].

Another

gen-

eralization

of

hypermetric

inequalities for

the

multicut

polytope

is

presented

in

Chopra

and

Rao

[1995].

Observe

that,

if

we

suppose

that

eJ

;:::

2,

then

the

inequality:

becomes valid for all even

multicut

vectors, i.e.,

the

vectors

6(8

1

,

...

, 8

p

)

corre-

sponding

to

a

partition

of

Vn

where all

the

8;'s

have

an

even

cardinality

(Deza

and

Laurent

[1993b]).

M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,

Chapter

29.

Clique-Web

Inequalities

We have

seen

in

Chapter

28

that

a valid

inequality

for

CUT

n

,

namely

the

hyper-

metric

inequality

Q(b)T x

::::;

0,

can

be

constructed

for any integer

vector

b E

zn

with

~i=l

b

i

=

1.

More generally, how

can

we

construct

a valid

inequality

if

we

have

an

arbitrary

integer

vector

b E

zn

?

When

~i=l

bi

= 3, we

can

construct

a valid

inequality

for

CUTn

in

the

following way.

Let

{1,

2,

...

,p}

denote

the

set

of

indices i for

which

bi

is

positive

and

suppose

that

3

::::;

p

::::;

n - 1.

Let

C

denote

a

circuit

with

node

set

{1,

...

,p}.

Then,

the

inequality:

(29.0.1)

L bibjXij - L

Xij::::;

0

l:;i<j:;n ijEE(C)

is valid for

CUT

n

. (Indeed,

the

value

of

the

left

hand

side

of

(29.0.1)

at

a

cut

vector

8(S)

is

b(S)(3

-

b(S))

-18(S)

n E(C)I,

which

is

nonpositive

if

b(S)

::::;

0

or

if

b(S)

?:

3;

if

b(S)

=

1,2,

then

b(S)(3-b(S))

= 2

and

1

::::;

ISn{1,

...

,p}1

::::;

p-1

which

implies

that

18(S) n E(C)I

?:

2.)

In

fact,

the

inequality

(29.0.1)

remains

valid

if

we

replace

the

circuit

C

by

an

arbitrary

2-edge

connected

graph

with

node

set

{1,

...

,p}.

However,

we

will consider here

only

the

case

of

a circuit.

It

is

an

open

problem

to

characterize

the

2-edge

connected

graphs

for

which

(29.0.1)

is facet

inducing

for CUTn-

We

describe

in

this

chapter

how

to

construct,

more

generally, a valid inequal-

ity

for

CUTn

for

any

b E

zn

with

~~1

bi

=

2r

+ 1

(r

?:

1). We

present

the

class

of

clique-web

inequalities

(CW~)Tx

::::;

O.

They

are

of

the

form (29.0.1),

with

the

circuit

C

being

replaced

by

a

more

complicated

graph,

namely, a

weighted

antiweb.

We will see

later

in

Section 30.1

the

class

of

suspended-tree

inequalities,

where

the

circuit

C is

replaced

by

a

suspended-tree.

29.1

Pure

Clique-Web

Inequalities

We first

introduce

the

clique-web

inequality

CW~

(b)T x

::::;

0

in

its

pure

form, i.e.,

in

the

case

when

Ibil

= 1 for all i.

Definition

29.1.1.

Given

integers

p

and

r

with

p

?:

2r

+ 3,

the

antiweb

AW;,

with

parameters

p

and

r,

is

the

graph

with

node

set

Vp

=

{1,

2,

...

p}

whose

edges

are

the

pairs

(i, i +

1),

(i, i +

2),

...

(i, i +

r)

for

i E

Vp

(the

indices

being

taken

modulo

p).

The

web

W;

is

the

complement

in

the

complete

graph

Kp

of

the

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.