text: 8 FIG. 7. (Color online) (a) Strain tensor components for a AlN/GaN supperlattice. (b) Piezoelectric ﬁeld and piezoelectric potential for a AlN/GaN supperlattice. Flat band Influence of piezo-electric potential with spontanoeous polarization on the flat band Influence of piezo-electric potential without spontanoeous polarization on the flat band 7 6 5 ) (a) Electron V 4 e ( y 3 g r e 2 n E (b) Hole 1 0 -1 -3 -2 -1 0 1 2 3 Distance, z (nm) FIG. 8. (Color online) Inﬂuence of piezo-electromechanical eﬀects on the band structure calculations of wurtzite AlN/GaN supperllatice. FIG. 9. (Color online) Inﬂuence of piezo-electromechanical eﬀects on the band structure calculations of wurtzite AlN/GaN supperllatice. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

text: (Color

text: online)

text: (a)

text: Strain

text: tensor

text: components

text: for

text: a

text: AlN/GaN

text: supperlattice.

text: (b)

text: Piezoelectric

text: ﬁeld

text: and

text: piezoelectric

text: potential

text: for

text: a

text: AlN/GaN

text: supperlattice.

text: Flat

text: band

text: Influence

text: of

text: piezo-electric

text: potential

text: with

text: spontanoeous

text: polarization

text: on

text: the

text: flat

text: band

text: Influence

text: of

text: piezo-electric

text: potential

text: without

text: spontanoeous

text: polarization

text: on

text: the

text: flat

text: band

text: (a)

text: Electron

text: V

text: e

text: y

text: g

text: r

text: e

text: n

text: E

text: (b)

text: Hole

text: Distance,

text: z

text: (nm)

text: FIG.

text: (Color

text: online)

text: Inﬂuence

text: of

text: piezo-electromechanical

text: eﬀects

text: on

text: the

text: band

text: structure

text: calculations

text: of

text: wurtzite

text: AlN/GaN

text: supperllatice.

text: FIG.

text: (Color

text: online)

text: Inﬂuence

text: of

text: piezo-electromechanical

text: eﬀects

text: on

text: the

text: band

text: structure

text: calculations

text: of

text: wurtzite

text: AlN/GaN

text: supperllatice.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 9 (a) Electron (b) Hole FIG. 10. (Color online) Conduction band ground state (Fig.a) and valence band ground state (Fig.b) in symmetric Al Ga − N/GaN/Al Ga − N NWSL structures with Al mole fraction x=0.01. Notice that the wavefunctions spread into x 1 x x 1 x the barrier material which indicates that the barrier material acts as an inversion layer. FIG. 11. (Color online) Subband energy levels of electrons and holes vs Al mole fraction in symmetric Al Ga − N/GaN/Al Ga − N NWSL structures. x 1 x x 1 x  (cid:16) (cid:17)  H(cid:101)(cid:101) = −−AA(cid:48)2(cid:48)1a∂2z2∂(r2+ε−−−−rUˆ1ˆ1riPPmcm+rr122+P2∂∂ε2φzra−φ1)εr1z∂zr+ˆ1 (cid:32)(cid:18)−−+−imMi+MLLnN1Uˆ1(cid:48)1121(cid:48)1ε2(cid:48)P(cid:2)vε∂mφ(cid:104)r∂(cid:2)6r2r2φ2∂mrz2r(cid:0)+mrr+∂−−+∂+lrr+1mi∂M+ε+(cid:52)rr1i2r2(cid:52)(cid:3)rr1ε3r1∂rmz+σ∂(cid:3)22(cid:1)z2zzy+σ(cid:105)(cid:19)z+ˆ1(cid:33)ˆ1 (cid:32)−−−+iML+iiMlNL(cid:48)11U11(cid:48)1ε2(cid:48)mvr(cid:2)∂φ(cid:104)m2∂6r2rφmr2ir+∂mm−+r+z∂rPmrM−m+2∂1+r22iεi(cid:52)ε∂(cid:52)r1rrzmzr2(cid:3)223z+σσ(cid:105)zx(cid:33)ˆ1 −(cid:18)−M−−L3(cid:48)2iNN(cid:104)∂2(cid:48)∂z22(cid:48)∂+r2+mrriˆ1+∂(cid:52)∂PUzz31r1v+σ∂1∂−zyrn+i2−(cid:52)lε2r3mεrzσz2(cid:19)2xz(cid:105)ˆ1ˆ1, (58) +m3 (εrr + εφφ) (cid:0) (cid:1) − − where ∂T = ∂ + r 1 and the matrix m has the We have used the Finite Element Method (FEM)31 r r form: (cid:18) (cid:19) and solve the correspondin·g eigenvalue problem of fully strain dependent 8-band k p Hamiltonian in 3D Carte- sian coordinates and in 2D cylindrical coordinates. For − m 1 0 3D solutions (both electromechanical and band structure m = 2 . (59) 0 m + 1 calculations), we have imposed Neumann boundary con- 2 ditions i.e., the continuity equation must hold at the heterojunction which is also referred to as the internal By identifying ε +ε = ∂ u +u /r+2a (see Eqs. 17 rr φφ r r r boundaries. Dirichlet boundary conditions are imposed and 18) in cylindrical coordinates, we veriﬁed that the · on the rest of the boundary. For cylindrically symmetric total strain dependent 8-band k p Hamiltonian (58) in 2D model, we deﬁne the z axis to be perpendicular to cylindrical coordinates are rotationally invariant with re- the plane of the quantum-well layer and r axis that lies spect to the rotation around the c-axis. in the quantum-well plane. For electromechanical parts, IV. COMPUTATIONAL METHOD: we have imposed u = 0, ∂ u = 0 and ∂ V = 0 along r z z r ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: (a)

font: default

text: Electron

text: (b)

text: Hole

text: FIG.

text: (Color

label: caption

text: online)

text: Conduction

text: band

text: ground

text: state

text: (Fig.a)

text: and

text: valence

text: band

text: ground

text: state

text: (Fig.b)

text: in

text: symmetric

text: Al

text: Ga

text: N/GaN/Al

text: Ga

text: N

text: NWSL

text: structures

text: with

text: Al

text: mole

text: fraction

text: Notice

text: that

text: the

text: wavefunctions

text: spread

text: into

text: x

text: x

text: x

text: x

text: the

text: barrier

text: material

text: which

text: indicates

text: that

text: the

text: barrier

text: material

text: acts

text: as

text: an

text: inversion

text: layer.

text: FIG.

text: (Color

text: online)

text: Subband

text: energy

text: levels

text: of

text: electrons

text: and

text: holes

text: vs

text: Al

text: mole

text: fraction

text: in

text: symmetric

text: Al

text: Ga

text: N/GaN/Al

text: Ga

text: N

text: NWSL

text: structures.

text: x

text: x

text: x

text: x

label: equation

text: (εrr

text: εφφ)

text: where

text: ∂T

text: r

text: and

text: the

text: matrix

text: m

text: has

text: the

text: We

text: have

text: used

text: the

text: Finite

text: Element

text: Method

text: r

text: r

text: form:

text: and

text: solve

text: the

text: correspondin·g

text: eigenvalue

text: problem

text: of

text: fully

text: strain

text: dependent

text: k

text: p

text: Hamiltonian

text: in

text: Carte-

text: sian

text: coordinates

text: and

text: in

text: cylindrical

text: coordinates.

text: For

text: m

text: solutions

text: (both

text: electromechanical

text: and

text: band

text: structure

text: m

text: m

text: calculations),

text: we

text: have

text: imposed

text: Neumann

text: boundary

text: con-

text: ditions

text: i.e.,

text: the

text: continuity

text: equation

text: must

text: hold

text: at

text: the

text: heterojunction

text: which

text: is

text: also

text: referred

text: to

text: as

text: the

text: internal

text: By

text: identifying

text: ε

text: +ε

text: u

text: +u

text: (see

text: Eqs.

text: rr

text: φφ

text: r

text: r

text: r

text: boundaries.

text: Dirichlet

text: boundary

text: conditions

text: are

text: imposed

text: and

text: in

text: cylindrical

text: coordinates,

text: we

text: veriﬁed

text: that

text: the

text: on

text: the

text: rest

text: of

text: the

text: boundary.

text: For

text: cylindrically

text: symmetric

text: total

text: strain

text: dependent

text: k

text: p

text: Hamiltonian

text: in

text: model,

text: we

text: deﬁne

text: the

text: z

text: axis

text: to

text: be

text: perpendicular

text: to

text: cylindrical

text: coordinates

text: are

text: rotationally

text: invariant

text: with

text: re-

text: the

text: plane

text: of

text: the

text: quantum-well

text: layer

text: and

text: r

text: axis

text: that

text: lies

text: spect

text: to

text: the

text: rotation

text: around

text: the

text: c-axis.

text: in

text: the

text: quantum-well

text: plane.

text: For

text: electromechanical

text: parts,

text: IV.

text: COMPUTATIONAL

text: METHOD:

text: we

text: have

text: imposed

text: u

text: u

text: and

text: V

text: along

text: r

text: z

text: z

text: r

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Unbalanced allocations ∗ Amanda Redlich May 26, 2020 Abstract We consider the unbalanced allocation of m balls into n bins by a randomized algorithm using the “power of two choices”. For each ball, we select a set of bins at random, then place the ball in the fullest bin within the set. Applications of this generic algorithm range from cost minimization to condensed matter physics. In this paper, we analyze the distribution of the bin loads produced by this algorithm, considering, for example, largest and smallest loads, loads of subsets of the bins, and the likelihood of bins having equal loads. 1 Introduction Balanced allocations are a well-studied area in computer science. A simple example is shoppers selecting cashiers at a grocery store; in a balanced allocation, most lines would be of the same (short) length. More technical applications include allocating servers in a network, allocating disks for storage, and hashing (see e.g. [3]). In all of these settings, the goal is to balance loads across all of the possible sites. There are many situations in which the opposite is the case. A simple example is select- ing ﬁlms at a multiplex; most ﬁlmgoers are wary of short lines and choose the ﬁlms with longer lines, assuming the popular ones are better. This forms an unbalanced allocation, with many empty loads and a few very large ones. There are many settings in which an unbalanced allocation appears. For example, if the options are priced with a buy-at-bulk discount, the cost of an unbalanced allocation is much lower than a balanced one. An unbalanced allocation also arises in natural processes; for example, condensed matter physics, smog and cloud formation, and galactic clustering in astrophysics (see e.g. [11]). This paper presents a generic unbalanced allocation algorithm and analyzes its behavior. This fundamental analysis provides a framework for developing algorithms that minimize ∗ Department of Mathematics, Bowdoin College, 8600 College Station, Brunswick ME 04011 (aredlich@bowdoin.edu). This material is based in part upon work supported by the National Science Foundation under Award No. 1004382. 1 ##LTLine##

text: Unbalanced

label: title

text: allocations

label: author

text: Amanda

text: Redlich

text: May

text: Abstract

text: We

label: abstract

text: consider

text: the

text: unbalanced

text: allocation

text: of

text: m

text: balls

text: into

text: n

text: bins

text: by

text: a

text: randomized

text: algorithm

text: using

text: the

text: “power

text: of

text: two

text: choices”.

text: For

text: each

text: ball,

text: we

text: select

text: a

text: set

text: of

text: bins

text: at

text: random,

text: then

text: place

text: the

text: ball

text: in

text: the

text: fullest

text: bin

text: within

text: the

text: set.

text: Applications

text: of

text: this

text: generic

text: algorithm

text: range

text: from

text: cost

text: minimization

text: to

text: condensed

text: matter

text: physics.

text: In

text: this

text: paper,

text: we

text: analyze

text: the

text: distribution

text: of

text: the

text: bin

text: loads

text: produced

text: by

text: this

text: algorithm,

text: considering,

text: for

text: example,

text: largest

text: and

text: smallest

text: loads,

text: loads

text: of

text: subsets

text: of

text: the

text: bins,

text: and

text: the

text: likelihood

text: of

text: bins

text: having

text: equal

text: loads.

text: Introduction

text: Balanced

text: allocations

text: are

text: a

text: well-studied

text: area

text: in

text: computer

text: science.

text: A

text: simple

text: example

text: is

text: shoppers

text: selecting

text: cashiers

text: at

text: a

text: grocery

text: store;

text: in

text: a

text: balanced

text: allocation,

text: most

text: lines

text: would

text: be

text: of

text: the

text: same

text: (short)

text: length.

text: More

text: technical

text: applications

text: include

text: allocating

text: servers

text: in

text: a

text: network,

text: allocating

text: disks

text: for

text: storage,

text: and

text: hashing

text: (see

text: e.g.

text: In

text: all

text: of

text: these

text: settings,

text: the

text: goal

text: is

text: to

text: balance

text: loads

text: across

text: all

text: of

text: the

text: possible

text: sites.

text: There

text: are

text: many

text: situations

text: in

text: which

text: the

text: opposite

text: is

text: the

text: case.

text: A

text: simple

text: example

text: is

text: select-

text: ing

text: ﬁlms

text: at

text: a

text: multiplex;

text: most

text: ﬁlmgoers

text: are

text: wary

text: of

text: short

text: lines

text: and

text: choose

text: the

text: ﬁlms

text: with

text: longer

text: lines,

text: assuming

text: the

text: popular

text: ones

text: are

text: better.

text: This

text: forms

text: an

text: unbalanced

text: allocation,

text: with

text: many

text: empty

text: loads

text: and

text: a

text: few

text: very

text: large

text: ones.

text: There

text: are

text: many

text: settings

text: in

text: which

text: an

text: unbalanced

text: allocation

text: appears.

text: For

text: example,

text: if

text: the

text: options

text: are

text: priced

text: with

text: a

text: buy-at-bulk

text: discount,

text: the

text: cost

text: of

text: an

text: unbalanced

text: allocation

text: is

text: much

text: lower

text: than

text: a

text: balanced

text: one.

text: An

text: unbalanced

text: allocation

text: also

text: arises

text: in

text: natural

text: processes;

text: for

text: example,

text: condensed

text: matter

text: physics,

text: smog

text: and

text: cloud

text: formation,

text: and

text: galactic

text: clustering

text: in

text: astrophysics

text: (see

text: e.g.

text: This

text: paper

text: presents

text: a

text: generic

text: unbalanced

text: allocation

text: algorithm

text: and

text: analyzes

text: its

text: behavior.

text: This

text: fundamental

text: analysis

text: provides

text: a

text: framework

text: for

text: developing

text: algorithms

text: that

text: minimize

text: Department

text: of

text: Mathematics,

text: Bowdoin

text: College,

text: College

text: Station,

text: Brunswick

text: ME

text: (aredlich@bowdoin.edu).

text: This

text: material

text: is

text: based

text: in

text: part

text: upon

text: work

text: supported

text: by

text: the

text: National

text: Science

text: Foundation

text: under

text: Award

text: No.

text: ##LTLine##


text: conﬁguration (1, 2, 1). We see that, if the tie is broken in favor of B at time t = 3 and 2 in favor of B at time t = 1, b (4) = 3 starting from (2, 1, 1) and b (4) = 2 starting from 3 2 2 (1, 2, 1). The eﬀect of bin B being larger initially is to make B smaller after more balls 2 2 have been placed. So in fact Lemma 11 is nontrivial. Proof. Our example paradox relied on the option sets intersecting. Ball placement at time 1 inﬂuenced placement at time 2, for example, because the option sets at times 1 and 2 were the same. In general, an extra ball in B can cause B to increase only if there is i j an intersection or chain of intersections between the option sets containing B and the { } { } { }i { } option sets containing B . For example, if the option sets are 3, i , 3, 4 , 5, 7 , 4, j , it j is possible that the behavior of B can inﬂuence B ; the decision between i and 3 made i j for S aﬀects the decision between 3 and 4 for S , which aﬀects the decision between 4 1 2 and j for S . To bound the probability of a paradox, we study the structure of option set 4 intersections. We call the elements aﬀected by the choice of B or B an “inﬂuence set”. In our { } { } { } {i } j { } previous example with option sets 3, i , 3, 4 , 5, 7 , 4, j , the inﬂuence set is i, 3, 4, j ; although 5 and 7 appear as options, there is no intersection or chain of intersections for B i and B that contain 5 or 7. j For ease of notation, assume we are comparing a placement in Bin 1 with Bin 2 (so the starting conﬁgurations are b + e and b + e ). Let T be the inﬂuence set at time t. { } 1 2 { }t Initially, T = 1, 2 . Given a sequence of option sets S , we can deﬁne T , the inﬂuence 0 t t set at time t, recursively. ∪ { | ∈ ∩ (cid:54) ∅} T = T − x x S and S T − = t t 1 t t t 1 { } { } { } { } { } In our example, T = i, j , T = i, j, 3 , T = i, j, 3, 4 , T = i, j, 3, 4 , T = i, j, 3, 4 . 0 1 2 3 4 As observed earlier, a paradox may arise only if a subsequent option set S contains B r 1 or B and some other bin which was already inﬂuenced by the initial choice of e or e . 2 1 2 (In our example, this happens for S .) We now bound the probability of this happening. 4 (cid:0) (cid:1) If S does contain both some index that is in T − and also B or B , then there must r r 1 1 2 ∈ be a subsequence of option sets St1, St2, . . . Sts−1, Sts = Sr such that for all i [s], Sti has a non-empty intersection with Sti−1, and St1 contains B1 or B2. There are rs choices for indices of a subsequence of length s. The probability that any particular length-s (cid:0) (cid:1) subsequence is intersecting is bounded by (d2/n)s. There are two choices for S and S (to t1 r contain B or B ), and the probability of either is less than d2/n. So the overall probability 1 2 of an intersecting sub(cid:18)seq(cid:19)uence of length s is bounded by 4 t (d2/n)s+1. (cid:88) s Then for the existence of such a sequence of any length, we have the bound t t ≤ ≤ 4 (d2/n)s+1 (4d2/n)(1 + d2/n)t (4d2/n)etd2/n. s s=1 − Note that when t = cn log n for c any constant, this is O(ncd2 1). In particular, if cd2 < 1, this is o(1). 15 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: conﬁguration

text: We

text: see

text: that,

text: if

text: the

text: tie

text: is

text: broken

text: in

text: favor

text: of

text: B

text: at

text: time

text: t

text: and

text: in

text: favor

text: of

text: B

text: at

text: time

text: t

text: b

text: starting

text: from

text: and

text: b

text: starting

text: from

text: The

text: eﬀect

text: of

text: bin

text: B

text: being

text: larger

text: initially

text: is

text: to

text: make

text: B

text: smaller

text: after

text: more

text: balls

text: have

text: been

text: placed.

text: So

text: in

text: fact

text: Lemma

text: is

text: nontrivial.

text: Proof.

text: Our

text: example

text: paradox

text: relied

text: on

text: the

text: option

text: sets

text: intersecting.

text: Ball

text: placement

text: at

text: time

text: inﬂuenced

text: placement

text: at

text: time

text: for

text: example,

text: because

text: the

text: option

text: sets

text: at

text: times

text: and

text: were

text: the

text: same.

text: In

text: general,

text: an

text: extra

text: ball

text: in

text: B

text: can

text: cause

text: B

text: to

text: increase

text: only

text: if

text: there

text: is

text: i

text: j

text: an

text: intersection

text: or

text: chain

text: of

text: intersections

text: between

text: the

text: option

text: sets

text: containing

text: B

text: and

text: the

text: }i

text: option

text: sets

text: containing

text: B

text: For

text: example,

text: if

text: the

text: option

text: sets

text: are

text: i

text: j

text: it

text: j

text: is

text: possible

text: that

text: the

text: behavior

text: of

text: B

text: can

text: inﬂuence

text: B

text: the

text: decision

text: between

text: i

text: and

text: made

text: i

text: j

text: for

text: S

text: aﬀects

text: the

text: decision

text: between

text: and

text: for

text: S

text: which

text: aﬀects

text: the

text: decision

text: between

text: and

text: j

text: for

text: S

text: To

text: bound

text: the

text: probability

text: of

text: a

text: paradox,

text: we

text: study

text: the

text: structure

text: of

text: option

text: set

text: intersections.

text: We

text: call

text: the

text: elements

text: aﬀected

text: by

text: the

text: choice

text: of

text: B

text: or

text: B

text: an

text: “inﬂuence

text: set”.

text: In

text: our

text: {i

text: j

text: previous

text: example

text: with

text: option

text: sets

text: i

text: j

text: the

text: inﬂuence

text: set

text: is

text: i,

text: j

text: although

text: and

text: appear

text: as

text: options,

text: there

text: is

text: no

text: intersection

text: or

text: chain

text: of

text: intersections

text: for

text: B

text: i

text: and

text: B

text: that

text: contain

text: or

text: j

text: For

text: ease

text: of

text: notation,

text: assume

text: we

text: are

text: comparing

text: a

text: placement

text: in

text: Bin

text: with

text: Bin

text: (so

text: the

text: starting

text: conﬁgurations

text: are

text: b

text: e

text: and

text: b

text: e

text: Let

text: T

text: be

text: the

text: inﬂuence

text: set

text: at

text: time

text: t.

text: }t

text: Initially,

text: T

text: Given

text: a

text: sequence

text: of

text: option

text: sets

text: S

text: we

text: can

text: deﬁne

text: T

text: the

text: inﬂuence

text: t

text: t

text: set

text: at

text: time

text: t,

text: recursively.

text: T

text: T

text: x

text: x

text: S

text: and

text: S

text: T

text: t

text: t

text: t

text: t

text: t

text: In

text: our

text: example,

text: T

text: i,

text: j

text: T

text: i,

text: j,

text: T

text: i,

text: j,

text: T

text: i,

text: j,

text: T

text: i,

text: j,

text: As

text: observed

text: earlier,

text: a

text: paradox

text: may

text: arise

text: only

text: if

text: a

text: subsequent

text: option

text: set

text: S

text: contains

text: B

text: r

text: or

text: B

text: and

text: some

text: other

text: bin

text: which

text: was

text: already

text: inﬂuenced

text: by

text: the

text: initial

text: choice

text: of

text: e

text: or

text: e

text: (In

text: our

text: example,

text: this

text: happens

text: for

text: S

text: We

text: now

text: bound

text: the

text: probability

text: of

text: this

text: happening.

text: If

text: S

text: does

text: contain

text: both

text: some

text: index

text: that

text: is

text: in

text: T

text: and

text: also

text: B

text: or

text: B

text: then

text: there

text: must

text: r

text: r

text: be

text: a

text: subsequence

text: of

text: option

text: sets

text: Sts

text: Sr

text: such

text: that

text: for

text: all

text: i

text: [s],

text: Sti

text: has

text: a

text: non-empty

text: intersection

text: with

text: and

text: contains

text: or

text: There

text: are

text: rs

text: choices

text: for

text: indices

text: of

text: a

text: subsequence

text: of

text: length

text: s.

text: The

text: probability

text: that

text: any

text: particular

text: length-s

text: subsequence

text: is

text: intersecting

text: is

text: bounded

text: by

text: There

text: are

text: two

text: choices

text: for

text: S

text: and

text: S

text: (to

text: r

text: contain

text: B

text: or

text: B

text: and

text: the

text: probability

text: of

text: either

text: is

text: less

text: than

text: So

text: the

text: overall

text: probability

text: of

text: an

text: intersecting

text: of

text: length

text: s

text: is

text: bounded

text: by

text: t

text: s

text: Then

text: for

text: the

text: existence

text: of

text: such

text: a

text: sequence

text: of

text: any

text: length,

text: we

text: have

text: the

text: bound

text: t

text: t

text: s

text: Note

text: that

text: when

text: t

text: cn

text: log

text: n

text: for

text: c

text: any

text: constant,

text: this

text: is

text: In

text: particular,

text: if

text: this

text: is

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: of a chain of intersection within the option sets is at most (4d2/n)etd2/n. Given that there is no chain of intersection, the placement of a ball into A or B at any of the important steps does not increase the load of the other bin. If v < u, the v sequence will generate AB a smaller B than the u sequence. (cid:0) (cid:1) Therefore the set of revealed sequences such that A and B have the same load is an − anti-chain under < with probability 1 O((d2/n)etd2/n). By Sperner’s Lemma, it has AB size at most q with the same probability. q/2 Now put these assumptions together. If there are exactly q important option sets, if the (cid:0) (cid:1) gap between the last (cid:15)n bins and A and B is as expected, and if the sequence of important sets is non-intersecting, the probability of A and B having the same number of balls after all m balls have been distributed is at most q /2q. q/2 It remains to ﬁnd values for (cid:15), δ, g, t, q, and γ. First consider δ. Note that, if A and B − (cid:48) are in the upper 1 δ proportion of bins at time m , then A and B have at least as many (cid:48) balls as the δnth bin at time m . That bin has at least as many balls as the average of the least δn bins’ loads. Recall the proof of Theorem 9 used the expected number of “good” steps and multiplied it by a correction factor to discount the times a ball placed within the least δn bins moved outside the least δn. In fact if the number of good steps is s, then the number of balls in − the least δn is at least sδ/(6 4δ). Note that the option sets are distributed uniformly, so we can use the standard Chernoﬀ bound (cid:48) − − (cid:48) P r(s < δdm α) < e 2α2/m (cid:48) to see that the number of balls in the last δ bins after the ﬁrst m steps is near the (cid:48) − − − − (cid:48) expectation, i.e. at least (δdm α)δ/(6 4δ), with probability at least 1 e 2α/m . Because the δnth bin has at least as many balls as the average, if A and B are in the upper − (1 δ)n bins, they will each have at least (cid:48) − − (δdm α)/(n)(6 4δ) balls with probability at least − − (cid:48) 1 e 2α2/m . (cid:48) Now turn to (cid:15). Suppose the number of balls in the least 2(cid:15)n bins at time m is x. Then the (cid:15)nth smallest bin would contain at most x/(cid:15)n balls. Recall that x is at most the number of times the option set is within the last 2(cid:15)n. The Chernoﬀ bound tells us that (cid:48) − (cid:48) P r(x > (2(cid:15))dm + β) < e 2β2/m . So the least (cid:15)n bins will each have loads at most (cid:48) 2d(cid:15)dm + β (cid:15)n 17 ##LTLine##

text: of

text: a

text: chain

text: of

text: intersection

text: within

text: the

text: option

text: sets

text: is

text: at

text: most

text: Given

text: that

text: there

text: is

text: no

text: chain

text: of

text: intersection,

text: the

text: placement

text: of

text: a

text: ball

text: into

text: A

text: or

text: B

text: at

text: any

text: of

text: the

text: important

text: steps

text: does

text: not

text: increase

text: the

text: load

text: of

text: the

text: other

text: bin.

text: If

text: v

text: u,

text: the

text: v

text: sequence

text: will

text: generate

text: AB

text: a

text: smaller

text: B

text: than

text: the

text: u

text: sequence.

text: Therefore

text: the

text: set

text: of

text: revealed

text: sequences

text: such

text: that

text: A

text: and

text: B

text: have

text: the

text: same

text: load

text: is

text: an

text: anti-chain

text: under

text: with

text: probability

text: By

text: Sperner’s

text: Lemma,

text: it

text: has

text: AB

text: size

text: at

text: most

text: q

text: with

text: the

text: same

text: probability.

text: Now

text: put

text: these

text: assumptions

text: together.

text: If

text: there

text: are

text: exactly

text: q

text: important

text: option

text: sets,

text: if

text: the

text: gap

text: between

text: the

text: last

text: bins

text: and

text: A

text: and

text: B

text: is

text: as

text: expected,

text: and

text: if

text: the

text: sequence

text: of

text: important

text: sets

text: is

text: non-intersecting,

text: the

text: probability

text: of

text: A

text: and

text: B

text: having

text: the

text: same

text: number

text: of

text: balls

text: after

text: all

text: m

text: balls

text: have

text: been

text: distributed

text: is

text: at

text: most

text: q

text: It

text: remains

text: to

text: ﬁnd

text: values

text: for

text: δ,

text: g,

text: t,

text: q,

text: and

text: γ.

text: First

text: consider

text: δ.

text: Note

text: that,

text: if

text: A

text: and

text: B

text: are

text: in

text: the

text: upper

text: δ

text: proportion

text: of

text: bins

text: at

text: time

text: m

text: then

text: A

text: and

text: B

text: have

text: at

text: least

text: as

text: many

text: balls

text: as

text: the

text: δnth

text: bin

text: at

text: time

text: m

text: That

text: bin

text: has

text: at

text: least

text: as

text: many

text: balls

text: as

text: the

text: average

text: of

text: the

text: least

text: δn

text: bins’

text: loads.

text: Recall

text: the

text: proof

text: of

text: Theorem

text: used

text: the

text: expected

text: number

text: of

text: “good”

text: steps

text: and

text: multiplied

text: it

text: by

text: a

text: correction

text: factor

text: to

text: discount

text: the

text: times

text: a

text: ball

text: placed

text: within

text: the

text: least

text: δn

text: bins

text: moved

text: outside

text: the

text: least

text: δn.

text: In

text: fact

text: if

text: the

text: number

text: of

text: good

text: steps

text: is

text: s,

text: then

text: the

text: number

text: of

text: balls

text: in

text: the

text: least

text: δn

text: is

text: at

text: least

text: Note

text: that

text: the

text: option

text: sets

text: are

text: distributed

text: uniformly,

text: so

text: we

text: can

text: use

text: the

text: standard

text: Chernoﬀ

text: bound

text: P

text: r(s

text: δdm

text: α)

text: e

text: to

text: see

text: that

text: the

text: number

text: of

text: balls

text: in

text: the

text: last

text: δ

text: bins

text: after

text: the

text: ﬁrst

text: m

text: steps

text: is

text: near

text: the

text: expectation,

text: i.e.

text: at

text: least

text: (δdm

text: with

text: probability

text: at

text: least

text: e

text: Because

text: the

text: δnth

text: bin

text: has

text: at

text: least

text: as

text: many

text: balls

text: as

text: the

text: average,

text: if

text: A

text: and

text: B

text: are

text: in

text: the

text: upper

text: δ)n

text: bins,

text: they

text: will

text: each

text: have

text: at

text: least

text: (δdm

text: balls

text: with

text: probability

text: at

text: least

text: e

text: Now

text: turn

text: to

text: Suppose

text: the

text: number

text: of

text: balls

text: in

text: the

text: least

text: bins

text: at

text: time

text: m

text: is

text: x.

text: Then

text: the

text: smallest

text: bin

text: would

text: contain

text: at

text: most

text: balls.

text: Recall

text: that

text: x

text: is

text: at

text: most

text: the

text: number

text: of

text: times

text: the

text: option

text: set

text: is

text: within

text: the

text: last

text: The

text: Chernoﬀ

text: bound

text: tells

text: us

text: that

text: P

text: r(x

text: β)

text: e

text: So

text: the

text: least

text: bins

text: will

text: each

text: have

text: loads

text: at

text: most

text: β

text: ##LTLine##


text: { } and S = 3, 4, 6 , the ball goes into bin B and at time t + 1, the conﬁguration is t 3(t) (b (t + 1), b (t + 1), . . . b (t + 1)) = (3, 2, 2, 1, 1, 0). 1(t+1) 2(t+1) 6(t+1) Even though the option set was within the least (2/3)n bins, the load of the least (2/3)n bins didn’t change. We now ﬁnd a lower bound on the number of balls in the least xn bins which holds for arbitrary m, n, d, x. The proof of this theorem uses a more in-depth analysis of possible conﬁgurations and is fairly involved. For ease of exposition, we give a simpliﬁed proof here. Theorem 9. For all values of m, n, and d, we have the following lower bounds on the expected number of balls under GREE(cid:18)DY(m(cid:19), n, d) in the smallest xn bins. When xn > d, the expected number is at least 1 xd+1m. 2ed ≤ When 1 < xn d, the expected number is at least − e dxdm. When xn = 1, the expected number is at least xd+1m. Proof. The contradictory behavior in our example above happened because the ﬁrst, sec- ond, and third bins had the same load. When the (xn + j)th bin is given a ball, the − − (xn k)th bin increases if and only if the bins between the (xn k)th and the (xn + j)th − − all had the same load, and the (xn k 1)st bin was larger. More formally, when i (t) = xn + j, m then b (t) = b (t + 1) (xn+j)(t) (xn+j)(t+1) and b − (t) + 1 = b − (t + 1), (xn k)(t) (xn k)(t+1) if and only if b − − (t) > b − (t) = b − (t) = . . . = b (t). xn k 1 (xn k)(t) (xn k+1)(t) (xn+j)(t) In order to ﬁnd a lower bound on the load of the last x bins, we will bound the probability of a string of equally-loaded bins. We here give the main ideas of the proof, using simple parameters. The bounds in Theorem 9 are found by optimizing these parameters. We bound how many balls are in 9 ##LTLine##

text: and

text: S

text: the

text: ball

text: goes

text: into

text: bin

text: B

text: and

text: at

text: time

text: t

text: the

text: conﬁguration

text: is

text: t

text: (b

text: (t

text: b

text: (t

text: b

text: (t

text: Even

text: though

text: the

text: option

text: set

text: was

text: within

text: the

text: least

text: bins,

text: the

text: load

text: of

text: the

text: least

text: bins

text: didn’t

text: change.

text: We

text: now

text: ﬁnd

text: a

text: lower

text: bound

text: on

text: the

text: number

text: of

text: balls

text: in

text: the

text: least

text: xn

text: bins

text: which

text: holds

text: for

text: arbitrary

text: m,

text: n,

text: d,

text: x.

text: The

text: proof

text: of

text: this

text: theorem

text: uses

text: a

text: more

text: in-depth

text: analysis

text: of

text: possible

text: conﬁgurations

text: and

text: is

text: fairly

text: involved.

text: For

text: ease

text: of

text: exposition,

text: we

text: give

text: a

text: simpliﬁed

text: proof

text: here.

text: Theorem

text: For

text: all

text: values

text: of

text: m,

text: n,

text: and

text: d,

text: we

text: have

text: the

text: following

text: lower

text: bounds

text: on

text: the

text: expected

text: number

text: of

text: balls

text: under

text: n,

text: d)

text: in

text: the

text: smallest

text: xn

text: bins.

text: When

text: xn

text: d,

text: the

text: expected

text: number

text: is

text: at

text: least

text: When

text: xn

text: d,

text: the

text: expected

text: number

text: is

text: at

text: least

text: e

text: dxdm.

text: When

text: xn

text: the

text: expected

text: number

text: is

text: at

text: least

text: Proof.

text: The

text: contradictory

text: behavior

text: in

text: our

text: example

text: above

text: happened

text: because

text: the

text: ﬁrst,

text: sec-

text: ond,

text: and

text: third

text: bins

text: had

text: the

text: same

text: load.

text: When

text: the

text: (xn

text: j)th

text: bin

text: is

text: given

text: a

text: ball,

text: the

text: (xn

text: k)th

text: bin

text: increases

text: if

text: and

text: only

text: if

text: the

text: bins

text: between

text: the

text: (xn

text: k)th

text: and

text: the

text: (xn

text: j)th

text: all

text: had

text: the

text: same

text: load,

text: and

text: the

text: (xn

text: k

text: bin

text: was

text: larger.

text: More

text: formally,

text: when

text: i

text: (t)

text: xn

text: j,

text: m

text: then

text: b

text: (t)

text: b

text: (t

text: (xn+j)(t)

text: and

text: b

text: (t)

text: b

text: (t

text: (xn

text: k)(t)

text: (xn

text: if

text: and

text: only

text: if

text: b

text: (t)

text: b

text: (t)

text: b

text: (t)

text: b

text: (t).

text: xn

text: k

text: (xn

text: k)(t)

text: (xn

text: (xn+j)(t)

text: In

text: order

text: to

text: ﬁnd

text: a

text: lower

text: bound

text: on

text: the

text: load

text: of

text: the

text: last

text: x

text: bins,

text: we

text: will

text: bound

text: the

text: probability

text: of

text: a

text: string

text: of

text: equally-loaded

text: bins.

text: We

text: here

text: give

text: the

text: main

text: ideas

text: of

text: the

text: proof,

text: using

text: simple

text: parameters.

text: The

text: bounds

text: in

text: Theorem

text: are

text: found

text: by

text: optimizing

text: these

text: parameters.

text: We

text: bound

text: how

text: many

text: balls

text: are

text: in

text: ##LTLine##


text: 2 clique j. A graph is an interval graph if and only if its clique matrices have the consecutive-ones property, see, for example, [6]. In 1962, Lekkerkerker and Boland described the minimal induced forbidden subgraphs for the class of interval graphs [10], known as the LB graphs. These are depicted in Figure 1. Ten years later, Tucker described the minimal forbidden submatrices for consecutive-ones matrices [24]. These are the matrices that do not have the consecutive-ones property, but where deletion of any row or column results in a matrix that has the consecutive-ones property. These are depicted in Figure 2. The presence of an induced LB subgraph in a graph and the presence of a Tucker submatrix in its clique matrix are both necessary and suﬃcient conditions for a graph not to be an interval graph. Not surprisingly, there is a relationship between the Tucker matrices and the clique matrices of LB graphs, depicted in Figure 3. ≥ G G G (n), n 4 I II III ≥ ≥ G (n), n 6 G (n), n 6 IV V Fig. 1: The Lekkerkerker-Boland subgraphs. In this paper, we give a linear time bound for ﬁnding an induced LB subgraph when a graph is not an interval graph. As part of our algorithm, we also give a linear-time (O(size(M)) bound for ﬁnding one of Tucker’s submatrices in a matrix M that does not have the consecutive-ones property. This latter problem ∗ was solved previously in O(n size(M)) time in [22]. An O(∆3m2n(m + n2) bound for ﬁnding a Tucker submatrix of minimum size is given in [5], where ∆ is the maximum number of 1’s in any row. A simplicial vertex of a graph is a vertex that occupies a single clique; it and its neighbors are the members of the clique. In Figure 3, the square vertices are the simplicial vertices. A chord on a path or cycle in a graph is an edge that is not on the cycle or path, but both of whose endpoints lie on the cycle or path. A chordless cycle in a graph is a cycle on four or more vertices that ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: clique

text: j.

text: A

text: graph

text: is

text: an

text: interval

text: graph

text: if

text: and

text: only

text: if

text: its

text: clique

text: matrices

text: have

text: the

text: consecutive-ones

text: property,

text: see,

text: for

text: example,

text: In

text: Lekkerkerker

text: and

text: Boland

text: described

text: the

text: minimal

text: induced

text: forbidden

text: subgraphs

text: for

text: the

text: class

text: of

text: interval

text: graphs

text: known

text: as

text: the

text: LB

text: graphs.

text: These

text: are

text: depicted

text: in

text: Figure

text: Ten

text: years

text: later,

text: Tucker

text: described

text: the

text: minimal

text: forbidden

text: submatrices

text: for

text: consecutive-ones

text: matrices

text: These

text: are

text: the

text: matrices

text: that

text: do

text: not

text: have

text: the

text: consecutive-ones

text: property,

text: but

text: where

text: deletion

text: of

text: any

text: row

text: or

text: column

text: results

text: in

text: a

text: matrix

text: that

text: has

text: the

text: consecutive-ones

text: property.

text: These

text: are

text: depicted

text: in

text: Figure

text: The

text: presence

text: of

text: an

text: induced

text: LB

text: subgraph

text: in

text: a

text: graph

text: and

text: the

text: presence

text: of

text: a

text: Tucker

text: submatrix

text: in

text: its

text: clique

text: matrix

text: are

text: both

text: necessary

text: and

text: suﬃcient

text: conditions

text: for

text: a

text: graph

text: not

text: to

text: be

text: an

text: interval

text: graph.

text: Not

text: surprisingly,

text: there

text: is

text: a

text: relationship

text: between

text: the

text: Tucker

text: matrices

text: and

text: the

text: clique

text: matrices

text: of

text: LB

text: graphs,

text: depicted

text: in

text: Figure

text: G

text: G

text: G

text: (n),

text: n

text: I

text: II

text: III

text: G

text: (n),

text: n

text: G

text: (n),

text: n

text: IV

text: V

text: Fig.

text: The

text: Lekkerkerker-Boland

text: subgraphs.

text: In

text: this

text: paper,

text: we

text: give

text: a

text: linear

text: time

text: bound

text: for

text: ﬁnding

text: an

text: induced

text: LB

text: subgraph

text: when

text: a

text: graph

text: is

text: not

text: an

text: interval

text: graph.

text: As

text: part

text: of

text: our

text: algorithm,

text: we

text: also

text: give

text: a

text: linear-time

text: (O(size(M))

text: bound

text: for

text: ﬁnding

text: one

text: of

text: Tucker’s

text: submatrices

text: in

text: a

text: matrix

text: M

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: This

text: latter

text: problem

text: was

text: solved

text: previously

text: in

text: O(n

text: size(M))

text: time

text: in

text: An

text: bound

text: for

text: ﬁnding

text: a

text: Tucker

text: submatrix

text: of

text: minimum

text: size

text: is

text: given

text: in

text: where

text: is

text: the

text: maximum

text: number

text: of

text: in

text: any

text: row.

text: A

text: simplicial

text: vertex

text: of

text: a

text: graph

text: is

text: a

text: vertex

text: that

text: occupies

text: a

text: single

text: clique;

text: it

text: and

text: its

text: neighbors

text: are

text: the

text: members

text: of

text: the

text: clique.

text: In

text: Figure

text: the

text: square

text: vertices

text: are

text: the

text: simplicial

text: vertices.

text: A

text: chord

text: on

text: a

text: path

text: or

text: cycle

text: in

text: a

text: graph

text: is

text: an

text: edge

text: that

text: is

text: not

text: on

text: the

text: cycle

text: or

text: path,

text: but

text: both

text: of

text: whose

text: endpoints

text: lie

text: on

text: the

text: cycle

text: or

text: path.

text: A

text: chordless

text: cycle

text: in

text: a

text: graph

text: is

text: a

text: cycle

text: on

text: four

text: or

text: more

text: vertices

text: that

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 13 Lemma 6. Suppose TuckerRows (Algorithm 3) is run with parameter k and a matrix M that does not have the consecutive-ones property. If the returned matrix (cid:48) M has at most k rows, then these are the rows of every Tucker submatrix in (cid:48) (cid:48) M . Otherwise, M fails to have the consecutive-ones property and every Tucker (cid:48) (cid:48) submatrix in M contains the ﬁrst k + 1 rows of M . Proof. By induction on i, M does not have the consecutive-ones property at the end of iteration i. Also by induction on i, using Lemma 5, at the end of iteration i, either M has at least i rows and every Tucker submatrix in M contains the − ﬁrst i rows of M, or else M has only i 1 rows and every Tucker submatrix in M − contains these i 1 rows, in which case M is returned before another iteration takes place. ∗ Lemma 7. Algorithm 3 takes O(k size(M)) time. Proof. It has at most k+1 iterations of the loop, each of which takes O(size(M)) time by Lemma 1. 4.2 FindRows Since Algorithm 2 only calls the remaining procedures if TuckerRows returns a submatrix with at least ﬁve rows, we may assume the following henceforth, by Lemma 6: – M is a matrix that does not have the consecutive-ones property and where every Tucker submatrix contains the ﬁrst ﬁve rows of M. The purpose of FindRows is to ﬁnd the rows of a Tucker submatrix in a matrix meeting this condition. Since M and M have only four rows, we IV V may exclude them from consideration. The only Tucker submatrices we need to consider henceforth are M , M , and M . I II III Proposition 1. The overlap graphs of M (k), M (k), and M (k) are simple I II III cycles. { } ∈ { } Let Z , Z , . . . , Z be the ﬁrst ﬁve rows of M. Let us choose Z Z , Z , . . . , Z , R(cid:48)1 2 5 1 2 5 and let be the remaining rows of M, excluding Z. Since every instance of a R(cid:48) R(cid:48)∪{ } Tucker submatrix contains Z, has the consecutive-ones property, but Z does not. Removal of one element from a chordless cycle gives a chordless path. There- R(cid:48) fore, we seek a chordless path in the overlap graph of that has the consecutive- ones property, and such that when we add Z to the rows on the path, they no longer have the consecutive-ones property. R(cid:48) R(cid:48) Deﬁnition 3. Let be a set of rows of M such that has the consecutive- R(cid:48) ∪ { } ∈ R(cid:48) ones property, but Z does not. Rows A, B are a suitable pair for Z R R(cid:48) if they are members of the same overlap component of , each of A and B Q R contains a 1 of Z, and in a consecutive-ones ordering of , a 0 of Z lies in Q between A and B. (See Figure 7.)

text: Lemma

text: Suppose

text: TuckerRows

text: (Algorithm

text: is

text: run

text: with

text: parameter

text: k

text: and

text: a

text: matrix

text: M

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: If

text: the

text: returned

text: matrix

text: M

text: has

text: at

text: most

text: k

text: rows,

text: then

text: these

text: are

text: the

text: rows

text: of

text: every

text: Tucker

text: submatrix

text: in

text: M

text: Otherwise,

text: M

text: fails

text: to

text: have

text: the

text: consecutive-ones

text: property

text: and

text: every

text: Tucker

text: submatrix

text: in

text: M

text: contains

text: the

text: ﬁrst

text: k

text: rows

text: of

text: M

text: Proof.

text: By

text: induction

text: on

text: i,

text: M

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property

text: at

text: the

text: end

text: of

text: iteration

text: i.

text: Also

text: by

text: induction

text: on

text: i,

text: using

text: Lemma

text: at

text: the

text: end

text: of

text: iteration

text: i,

text: either

text: M

text: has

text: at

text: least

text: i

text: rows

text: and

text: every

text: Tucker

text: submatrix

text: in

text: M

text: contains

text: the

text: ﬁrst

text: i

text: rows

text: of

text: M,

text: or

text: else

text: M

text: has

text: only

text: i

text: rows

text: and

text: every

text: Tucker

text: submatrix

text: in

text: M

text: contains

text: these

text: i

text: rows,

text: in

text: which

text: case

text: M

text: is

text: returned

text: before

text: another

text: iteration

text: takes

text: place.

text: Lemma

text: Algorithm

text: takes

text: O(k

text: size(M))

text: time.

text: Proof.

text: It

text: has

text: at

text: most

text: iterations

text: of

text: the

text: loop,

text: each

text: of

text: which

text: takes

text: O(size(M))

text: time

text: by

text: Lemma

text: FindRows

text: Since

text: Algorithm

text: only

text: calls

text: the

text: remaining

text: procedures

text: if

text: TuckerRows

text: returns

text: a

text: submatrix

text: with

text: at

text: least

text: ﬁve

text: rows,

text: we

text: may

text: assume

text: the

text: following

text: henceforth,

text: by

text: Lemma

text: M

text: is

text: a

text: matrix

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property

text: and

text: where

text: every

text: Tucker

text: submatrix

text: contains

text: the

text: ﬁrst

text: ﬁve

text: rows

text: of

text: M.

text: The

text: purpose

text: of

text: FindRows

text: is

text: to

text: ﬁnd

text: the

text: rows

text: of

text: a

text: Tucker

text: submatrix

text: in

text: a

text: matrix

text: meeting

text: this

text: condition.

text: Since

text: M

text: and

text: M

text: have

text: only

text: four

text: rows,

text: we

text: IV

text: V

text: may

text: exclude

text: them

text: from

text: consideration.

text: The

text: only

text: Tucker

text: submatrices

text: we

text: need

text: to

text: consider

text: henceforth

text: are

text: M

text: M

text: and

text: M

text: I

text: II

text: III

text: Proposition

text: The

text: overlap

text: graphs

text: of

text: M

text: (k),

text: M

text: (k),

text: and

text: M

text: (k)

text: are

text: simple

text: I

text: II

text: III

text: cycles.

text: Let

text: Z

text: Z

text: Z

text: be

text: the

text: ﬁrst

text: ﬁve

text: rows

text: of

text: M.

text: Let

text: us

text: choose

text: Z

text: Z

text: Z

text: Z

text: and

text: let

text: be

text: the

text: remaining

text: rows

text: of

text: M,

text: excluding

text: Z.

text: Since

text: every

text: instance

text: of

text: a

text: Tucker

text: submatrix

text: contains

text: Z,

text: has

text: the

text: consecutive-ones

text: property,

text: but

text: Z

text: does

text: not.

text: Removal

text: of

text: one

text: element

text: from

text: a

text: chordless

text: cycle

text: gives

text: a

text: chordless

text: path.

text: There-

text: fore,

text: we

text: seek

text: a

text: chordless

text: path

text: in

text: the

text: overlap

text: graph

text: of

text: that

text: has

text: the

text: consecutive-

text: ones

text: property,

text: and

text: such

text: that

text: when

text: we

text: add

text: Z

text: to

text: the

text: rows

text: on

text: the

text: path,

text: they

text: no

text: longer

text: have

text: the

text: consecutive-ones

text: property.

text: Deﬁnition

text: Let

text: be

text: a

text: set

text: of

text: rows

text: of

text: M

text: such

text: that

text: has

text: the

text: consecutive-

text: ones

text: property,

text: but

text: Z

text: does

text: not.

text: Rows

text: A,

text: B

text: are

text: a

text: suitable

text: pair

text: for

text: Z

text: R

text: if

text: they

text: are

text: members

text: of

text: the

text: same

text: overlap

text: component

text: of

text: each

text: of

text: A

text: and

text: B

text: Q

text: R

text: contains

text: a

text: of

text: Z,

text: and

text: in

text: a

text: consecutive-ones

text: ordering

text: of

text: a

text: of

text: Z

text: lies

text: in

text: Q

text: between

text: A

text: and

text: B.

text: (See

text: Figure


text: 17 P∪{ } Since Z does not have the consecutive-ones property, the shortest preﬁx P P P ∪{ } of such that Z does not have the consecutive-ones property exists. By 1 1 P P ∪ { } the deﬁnition of (Z, R , R , . . . , R ), = (R , R , . . . , R ). Since Z does 1 2 j 1 1 2 j P P1 not have the consecutive-ones property, the shortest suﬃx of such that P ∪ { } 2 1 Z does not have the consecutive-ones property exists. By the deﬁnition 2 P of (Z, R , R − , . . . , R ), = (R , R , . . . , R ). j j 1 i 2 i i+R1(cid:48) j P R(cid:48) ∪ { } Suppose there is a proper subset of the rows on such that Z P 2 does not have the consecutive-ones property. Since is a shortest path, it R(cid:48) P 2 R is a chordless path, so is a subpath of by Proposition 1. Let = 2 P 1 (R , R , . . . , R − ). This is the result of removing the last row from . Let R 1 2 j 1 1 P = (R , R , . . . , R ). This is the result of removing the ﬁrst row from . 2 i+1 i+2 P j P R ∪ { } R ∪ { } 2 By the minimality of and , Z and Z have the consecutive- R1(cid:48) 2 1 P2 R(cid:48) ⊆ R R(cid:48) ⊆ R ones property. Since is a proper subpath of , or , so R(cid:48) ∪ { } 2 1 2 Z has the consecutive-ones property, contradicting our assumption that P ∪ { } it does not. Therefore, Z is a minimal set of rows that does not have 2 the consecutive-ones property. It must be a minimal set of rows that contains an instance of a Tucker matrix. 4.3 Finding a suitable pair The procedure SuitablePair, which is called from FindRows (Algorithm 4), takes as a parameter a matrix M that does not have the consecutive-ones prop- erty and such that every instance of a Tucker submatrix in M contains the ﬁrst ﬁve rows. Lemma 9. Suppose a matrix M fails to have the consecutive-ones property, has no Tucker submatrix with fewer than ﬁve rows and every Tucker matrix { } ∈ { } R contains the rows Z , Z , Z , Z , Z . For each Z Z , Z , . . . , Z , let be 1 2 3 4 5 i 1 2 R 5 i the rows of M, excluding Z . For one of the ﬁve choices of Z , has an overlap i i i component with a suitable pair A, B for Z . i Proof. (See Figure 10.) Let M be an instance of Tucker submatrix in M. Since T M must have at least ﬁve rows, it is an instance of M (k), M (k) or M (k) T ≥ I II III for k 5. R For each choice of Z , has the consecutive-ones property, since every i i R Tucker matrix contains Z as one of its rows. Let be the rows of M , exclud- i R T T ing Z . A consecutive-ones ordering of imposes a consecutive-ones ordering on R i R i . Since the overlap graph of is connected, by Proposition 1, the ordering T R T of Venn classes of is unique, up to reversal, by Lemma 2. T Let the rows of M be numbered as in Figure 2. As shown in Figure 10, T ∈ { − − } − unless Z contains row i 0, 1, k 2, k 1 of M , rows i 1 and i + 1 of M i T T are a suitable pair for Z . There are at most four of the ﬁve choices of Z that i R i can fail to have a suitable pair in . i R(cid:48) R(cid:48) ∪ Lemma 10. Suppose a set of rows is consecutive-ones ordered, but but { } R Z does not have the consecutive-ones property. Let be the rows of an Q

text: P∪{

text: Since

text: Z

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property,

text: the

text: shortest

text: preﬁx

text: P

text: P

text: P

text: of

text: such

text: that

text: Z

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property

text: exists.

text: By

text: P

text: P

text: the

text: deﬁnition

text: of

text: (Z,

text: R

text: R

text: R

text: (R

text: R

text: R

text: Since

text: Z

text: does

text: j

text: j

text: P

text: not

text: have

text: the

text: consecutive-ones

text: property,

text: the

text: shortest

text: suﬃx

text: of

text: such

text: that

text: P

text: Z

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property

text: exists.

text: By

text: the

text: deﬁnition

text: P

text: of

text: (Z,

text: R

text: R

text: R

text: (R

text: R

text: R

text: j

text: j

text: i

text: i

text: j

text: P

text: Suppose

text: there

text: is

text: a

text: proper

text: subset

text: of

text: the

text: rows

text: on

text: such

text: that

text: Z

text: P

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: Since

text: is

text: a

text: shortest

text: path,

text: it

text: P

text: R

text: is

text: a

text: chordless

text: path,

text: so

text: is

text: a

text: subpath

text: of

text: by

text: Proposition

text: Let

text: P

text: (R

text: R

text: R

text: This

text: is

text: the

text: result

text: of

text: removing

text: the

text: last

text: row

text: from

text: Let

text: R

text: j

text: P

text: (R

text: R

text: R

text: This

text: is

text: the

text: result

text: of

text: removing

text: the

text: ﬁrst

text: row

text: from

text: P

text: j

text: P

text: R

text: R

text: By

text: the

text: minimality

text: of

text: and

text: Z

text: and

text: Z

text: have

text: the

text: consecutive-

text: R

text: R

text: ones

text: property.

text: Since

text: is

text: a

text: proper

text: subpath

text: of

text: or

text: so

text: Z

text: has

text: the

text: consecutive-ones

text: property,

text: contradicting

text: our

text: assumption

text: that

text: P

text: it

text: does

text: not.

text: Therefore,

text: Z

text: is

text: a

text: minimal

text: set

text: of

text: rows

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: It

text: must

text: be

text: a

text: minimal

text: set

text: of

text: rows

text: that

text: contains

text: an

text: instance

text: of

text: a

text: Tucker

text: matrix.

text: Finding

text: a

text: suitable

text: pair

text: The

text: procedure

text: SuitablePair,

text: which

text: is

text: called

text: from

text: FindRows

text: (Algorithm

text: takes

text: as

text: a

text: parameter

text: a

text: matrix

text: M

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: prop-

text: erty

text: and

text: such

text: that

text: every

text: instance

text: of

text: a

text: Tucker

text: submatrix

text: in

text: M

text: contains

text: the

text: ﬁrst

text: ﬁve

text: rows.

text: Lemma

text: Suppose

text: a

text: matrix

text: M

text: fails

text: to

text: have

text: the

text: consecutive-ones

text: property,

text: has

text: no

text: Tucker

text: submatrix

text: with

text: fewer

text: than

text: ﬁve

text: rows

text: and

text: every

text: Tucker

text: matrix

text: R

text: contains

text: the

text: rows

text: Z

text: Z

text: Z

text: Z

text: Z

text: For

text: each

text: Z

text: Z

text: Z

text: Z

text: let

text: be

text: i

text: R

text: i

text: the

text: rows

text: of

text: M,

text: excluding

text: Z

text: For

text: one

text: of

text: the

text: ﬁve

text: choices

text: of

text: Z

text: has

text: an

text: overlap

text: i

text: i

text: i

text: component

text: with

text: a

text: suitable

text: pair

text: A,

text: B

text: for

text: Z

text: i

text: Proof.

text: (See

text: Figure

text: Let

text: M

text: be

text: an

text: instance

text: of

text: Tucker

text: submatrix

text: in

text: M.

text: Since

text: T

text: M

text: must

text: have

text: at

text: least

text: ﬁve

text: rows,

text: it

text: is

text: an

text: instance

text: of

text: M

text: (k),

text: M

text: (k)

text: or

text: M

text: (k)

text: T

text: I

text: II

text: III

text: for

text: k

text: R

text: For

text: each

text: choice

text: of

text: Z

text: has

text: the

text: consecutive-ones

text: property,

text: since

text: every

text: i

text: i

text: R

text: Tucker

text: matrix

text: contains

text: Z

text: as

text: one

text: of

text: its

text: rows.

text: Let

text: be

text: the

text: rows

text: of

text: M

text: exclud-

text: i

text: R

text: T

text: T

text: ing

text: Z

text: A

text: consecutive-ones

text: ordering

text: of

text: imposes

text: a

text: consecutive-ones

text: ordering

text: on

text: R

text: i

text: R

text: i

text: Since

text: the

text: overlap

text: graph

text: of

text: is

text: connected,

text: by

text: Proposition

text: the

text: ordering

text: T

text: R

text: T

text: of

text: Venn

text: classes

text: of

text: is

text: unique,

text: up

text: to

text: reversal,

text: by

text: Lemma

text: T

text: Let

text: the

text: rows

text: of

text: M

text: be

text: numbered

text: as

text: in

text: Figure

text: As

text: shown

text: in

text: Figure

text: T

text: unless

text: Z

text: contains

text: row

text: i

text: k

text: k

text: of

text: M

text: rows

text: i

text: and

text: i

text: of

text: M

text: i

text: T

text: T

text: are

text: a

text: suitable

text: pair

text: for

text: Z

text: There

text: are

text: at

text: most

text: four

text: of

text: the

text: ﬁve

text: choices

text: of

text: Z

text: that

text: i

text: R

text: i

text: can

text: fail

text: to

text: have

text: a

text: suitable

text: pair

text: in

text: i

text: Lemma

text: Suppose

text: a

text: set

text: of

text: rows

text: is

text: consecutive-ones

text: ordered,

text: but

text: but

text: R

text: Z

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: Let

text: be

text: the

text: rows

text: of

text: an

text: Q


text: 19 R(cid:48) (cid:48) overlap component of . Let A be a row with the leftmost right endpoint such (cid:48) (cid:48) that A contains a column that has a 1 in row Z, and let B be a row with the (cid:48) rightmost left endpoint such that B contains a column that has a 1 of Z. Then (cid:48) (cid:48) (cid:48) (cid:48) A and B are a suitable pair for Z if A and B are disjoint, and a column that (cid:48) (cid:48) has a 0 in row Z occurs in between A and B . Otherwise no suitable pair for Z R exists in . Q (cid:48) (cid:48) Proof. If A and B satisfy the conditions, they are a suitable pair for Z, by ∈ R deﬁnition. Conversely, suppose there exist rows A, B that are a suitable Q pair for Z. Suppose without loss of generality that A is to the left of B. Then (cid:48) (cid:48) A can be substituted for A and B can be substituted for B, and the 0 of row (cid:48) (cid:48) { (cid:48) (cid:48)} Z that lies between A and B will also lie between A and B , hence A , B is a suitable pair for Z. The procedure is given as Algorithm 5. Algorithm 5: SuitablePair(M) Data: A matrix M that does not have the consecutive-ones property, and in which every Tucker submatrix contains the ﬁrst ﬁve rows of M Result: A row Z and a suitable pair A, B for Z (Deﬁnition 3) have been returned Let (Z , Z , . . . , Z ) be the ﬁrst ﬁve rows of M ; 1 2 5 for i = 1 to 5 do R Let be the rows of M, excluding Z ; i(cid:48) i R Let M be a consecutive-ones ordering of ; i (cid:48) Use OverlapBFS to ﬁnd the overlap components of M (Algorithm 1); R (cid:48) for each overlap component of M do (cid:48) RQ Let A be the member of with the leftmost right endpoint among Q rows that contain a 1 of Z ; (cid:48) R i Let B be the member of with the rightmost left endpoint among Q rows that contain a 1 of Z ; i (cid:48) (cid:48) if a 0 of Z occurs in between A and B then i (cid:48) (cid:48) return (A , B , Z ); i { } Lemma 11. SuitablePair(M) returns a triple (A, B, Z) such that A, B are a suitable pair for Z. ∈ Proof. By Lemma 9, a suitable pair exists for one of the ﬁve choices Z { } { (cid:48) i (cid:48)} Z , Z , . . . , Z . By Lemma 10, the procedure ﬁnds a suitable pair A , B 1 2 5 (cid:48) (cid:48) for Z returning (A , B , Z ). i i Lemma 12. SuitablePair(M) takes O(size(M)) time. R Proof. On each iteration i, we may ﬁnd a consecutive-ones ordering of in i O(size(M)) time. We may then label all columns of M with the value of Z in i ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: overlap

text: component

text: of

text: Let

text: A

text: be

text: a

text: row

text: with

text: the

text: leftmost

text: right

text: endpoint

text: such

text: that

text: A

text: contains

text: a

text: column

text: that

text: has

text: a

text: in

text: row

text: Z,

text: and

text: let

text: B

text: be

text: a

text: row

text: with

text: the

text: rightmost

text: left

text: endpoint

text: such

text: that

text: B

text: contains

text: a

text: column

text: that

text: has

text: a

text: of

text: Z.

text: Then

text: A

text: and

text: B

text: are

text: a

text: suitable

text: pair

text: for

text: Z

text: if

text: A

text: and

text: B

text: are

text: disjoint,

text: and

text: a

text: column

text: that

text: has

text: a

text: in

text: row

text: Z

text: occurs

text: in

text: between

text: A

text: and

text: B

text: Otherwise

text: no

text: suitable

text: pair

text: for

text: Z

text: R

text: exists

text: in

text: Q

text: Proof.

text: If

text: A

text: and

text: B

text: satisfy

text: the

text: conditions,

text: they

text: are

text: a

text: suitable

text: pair

text: for

text: Z,

text: by

text: R

text: deﬁnition.

text: Conversely,

text: suppose

text: there

text: exist

text: rows

text: A,

text: B

text: that

text: are

text: a

text: suitable

text: Q

text: pair

text: for

text: Z.

text: Suppose

text: without

text: loss

text: of

text: generality

text: that

text: A

text: is

text: to

text: the

text: left

text: of

text: B.

text: Then

text: A

text: can

text: be

text: substituted

text: for

text: A

text: and

text: B

text: can

text: be

text: substituted

text: for

text: B,

text: and

text: the

text: of

text: row

text: Z

text: that

text: lies

text: between

text: A

text: and

text: B

text: will

text: also

text: lie

text: between

text: A

text: and

text: B

text: hence

text: A

text: B

text: is

text: a

text: suitable

text: pair

text: for

text: Z.

text: The

text: procedure

text: is

text: given

text: as

text: Algorithm

text: Algorithm

text: SuitablePair(M)

text: Data:

text: A

text: matrix

text: M

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property,

text: and

text: in

text: which

text: every

text: Tucker

text: submatrix

text: contains

text: the

text: ﬁrst

text: ﬁve

text: rows

text: of

text: M

text: Result:

text: A

text: row

text: Z

text: and

text: a

text: suitable

text: pair

text: A,

text: B

text: for

text: Z

text: (Deﬁnition

text: have

text: been

text: returned

text: Let

text: (Z

text: Z

text: Z

text: be

text: the

text: ﬁrst

text: ﬁve

text: rows

text: of

text: M

text: for

text: i

text: to

text: do

text: R

text: Let

text: be

text: the

text: rows

text: of

text: M,

text: excluding

text: Z

text: i

text: R

text: Let

text: M

text: be

text: a

text: consecutive-ones

text: ordering

text: of

text: i

text: Use

text: OverlapBFS

text: to

text: ﬁnd

text: the

text: overlap

text: components

text: of

text: M

text: (Algorithm

text: R

text: for

text: each

text: overlap

text: component

text: of

text: M

text: do

text: RQ

text: Let

text: A

text: be

text: the

text: member

text: of

text: with

text: the

text: leftmost

text: right

text: endpoint

text: among

text: Q

text: rows

text: that

text: contain

text: a

text: of

text: Z

text: R

text: i

text: Let

text: B

text: be

text: the

text: member

text: of

text: with

text: the

text: rightmost

text: left

text: endpoint

text: among

text: Q

text: rows

text: that

text: contain

text: a

text: of

text: Z

text: i

text: if

text: a

text: of

text: Z

text: occurs

text: in

text: between

text: A

text: and

text: B

text: then

text: i

text: return

text: (A

text: B

text: Z

text: i

text: Lemma

text: SuitablePair(M)

text: returns

text: a

text: triple

text: (A,

text: B,

text: Z)

text: such

text: that

text: A,

text: B

text: are

text: a

text: suitable

text: pair

text: for

text: Z.

text: Proof.

text: By

text: Lemma

text: a

text: suitable

text: pair

text: exists

text: for

text: one

text: of

text: the

text: ﬁve

text: choices

text: Z

text: i

text: Z

text: Z

text: Z

text: By

text: Lemma

text: the

text: procedure

text: ﬁnds

text: a

text: suitable

text: pair

text: A

text: B

text: for

text: Z

text: returning

text: (A

text: B

text: Z

text: i

text: i

text: Lemma

text: SuitablePair(M)

text: takes

text: O(size(M))

text: time.

text: R

text: Proof.

text: On

text: each

text: iteration

text: i,

text: we

text: may

text: ﬁnd

text: a

text: consecutive-ones

text: ordering

text: of

text: in

text: i

text: O(size(M))

text: time.

text: We

text: may

text: then

text: label

text: all

text: columns

text: of

text: M

text: with

text: the

text: value

text: of

text: Z

text: in

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 26 P(cid:48) ∪{ } By Lemma 15, the returned submatrix, ( Z )[C], is a Tucker submatrix. Lemma 20. FindColumns(M) can be implemented to take O(size(M)) time. P(cid:48) Proof. A consecutive-ones ordering of takes O(size(M)) time by [1]. By Lemma 16, it takes O(size(M)) time to list the members of each instance \ ∩ \ ∈ { − } of R R , R R , and R R for i 1, 2, . . . , h 1 . This gives the i i+1A i i+1 i+1 i L members of , some of them possibly more than once. Let be this collection L of lists. Give each column a list of members of to which it belongs. Initialize a L cardinality counter on each list in , indicating the number of columns of C that it contains. These operations take O(size(M)) time using elementary methods, L given that the sum of lengths of the lists in is O(size(M)). LIn the ﬁrst for loop, each column ci is tested to see whether it one of the lists of that contains it has a cardinality counter of 1. If not, c is removed from L i C and the cardinality counters of the lists of that contain it are decremented. ∈ { } The total time for this loop is bounded by summing, over all c c , c , . . . , c , L i 1 2 k the number of members of that contain c . This is just the sum of cardinalities L i of lists in , hence O(size(M)). The procedure needs to test for or ﬁnd a 1-0-1 or a 0-1-0 conﬁguration on at most ﬁve occasions: two when it initially determines whether there is a 1-0-1 or 0-1-0 conﬁguration, thereby ﬁnding (c , c , c ), and three in one of the p(1) p(2) p(3 last two for loops, when it tests whether removal of c , c , and c leave p(1) p(2) p(3) a 1-0-1 or 0-1-0 conﬁguration. Each of these occasions requires O(size(M)) time by Lemma 18. Example: We give an illustration of how Algorithm 6 works on the example A { } { } of Figure 9 (bottom). consists of the following sets: 3, 4, . . . , 14 , 15 and { } { } { } { } 16 , which ensure the overlap relation of F and G, 16 , 15 , 12, 13, 14 , { } { } { } which ensure the overlap relation of G and H, 13, 14, 15 , 12 and 10, 11 , which ensure the overlap relation of H and J. Some of these sets are redundant, but there is no need to detect this. We put a cardinality counter on each of these sets, and decrement it whenever a column in the set is deleted. At least one column from each of these sets must be retained to maintain the connectivity of P(cid:48) the overlap graph of . { } C { } Initially, C = 0, 1, . . . , 16 , and = 3, 4, . . . , 16 . There is no 1-0-1 con- Q (cid:48) ﬁguration, so the algorithm retains a column c in the unconstrained class that (cid:48) contains a 1 in row Z. Suppose it selects c = 2. It eliminates the remaining columns 0 and 1 of the unconstrained class from C. It ﬁnds the 0-1-0 conﬁgura- tion (c , c , c ) = (4, 10, 12). p(1) p(2) p(3) { } The ﬁrst for loop eliminates all but columns 2, 4, 10, 12, 15, 16 ; 2 is skipped because it is a member of the unconstrained Venn class, 4, 10, and 12 are skipped because they are c , c and c , and 15 and 16 are retained because they are p(1) p(2) p(3) A the only remaining elements of some member of when they are reached. The ﬁnal for loop determines that elimination of 4 or 10 would undermine all 0-1-0 conﬁgurations, and elimination of 12 would remove the last remaining element { } A of the member 12 of .

text: By

text: Lemma

text: the

text: returned

text: submatrix,

text: Z

text: )[C],

text: is

text: a

text: Tucker

text: submatrix.

text: Lemma

text: FindColumns(M)

text: can

text: be

text: implemented

text: to

text: take

text: O(size(M))

text: time.

text: Proof.

text: A

text: consecutive-ones

text: ordering

text: of

text: takes

text: O(size(M))

text: time

text: by

text: By

text: Lemma

text: it

text: takes

text: O(size(M))

text: time

text: to

text: list

text: the

text: members

text: of

text: each

text: instance

text: of

text: R

text: R

text: R

text: R

text: and

text: R

text: R

text: for

text: i

text: h

text: This

text: gives

text: the

text: i

text: i

text: i

text: L

text: members

text: of

text: some

text: of

text: them

text: possibly

text: more

text: than

text: once.

text: Let

text: be

text: this

text: collection

text: L

text: of

text: lists.

text: Give

text: each

text: column

text: a

text: list

text: of

text: members

text: of

text: to

text: which

text: it

text: belongs.

text: Initialize

text: a

text: L

text: cardinality

text: counter

text: on

text: each

text: list

text: in

text: indicating

text: the

text: number

text: of

text: columns

text: of

text: C

text: that

text: it

text: contains.

text: These

text: operations

text: take

text: O(size(M))

text: time

text: using

text: elementary

text: methods,

text: L

text: given

text: that

text: the

text: sum

text: of

text: lengths

text: of

text: the

text: lists

text: in

text: is

text: O(size(M)).

text: LIn

text: the

text: ﬁrst

text: for

text: loop,

text: each

text: column

text: ci

text: is

text: tested

text: to

text: see

text: whether

text: it

text: one

text: of

text: the

text: lists

text: of

text: that

text: contains

text: it

text: has

text: a

text: cardinality

text: counter

text: of

text: If

text: not,

text: c

text: is

text: removed

text: from

text: L

text: i

text: C

text: and

text: the

text: cardinality

text: counters

text: of

text: the

text: lists

text: of

text: that

text: contain

text: it

text: are

text: decremented.

text: The

text: total

text: time

text: for

text: this

text: loop

text: is

text: bounded

text: by

text: summing,

text: over

text: all

text: c

text: c

text: c

text: c

text: L

text: i

text: k

text: the

text: number

text: of

text: members

text: of

text: that

text: contain

text: c

text: This

text: is

text: just

text: the

text: sum

text: of

text: cardinalities

text: L

text: i

text: of

text: lists

text: in

text: hence

text: O(size(M)).

text: The

text: procedure

text: needs

text: to

text: test

text: for

text: or

text: ﬁnd

text: a

text: or

text: a

text: conﬁguration

text: on

text: at

text: most

text: ﬁve

text: occasions:

text: two

text: when

text: it

text: initially

text: determines

text: whether

text: there

text: is

text: a

text: or

text: conﬁguration,

text: thereby

text: ﬁnding

text: (c

text: c

text: c

text: and

text: three

text: in

text: one

text: of

text: the

text: last

text: two

text: for

text: loops,

text: when

text: it

text: tests

text: whether

text: removal

text: of

text: c

text: c

text: and

text: c

text: leave

text: a

text: or

text: conﬁguration.

text: Each

text: of

text: these

text: occasions

text: requires

text: O(size(M))

text: time

text: by

text: Lemma

text: Example:

text: We

text: give

text: an

text: illustration

text: of

text: how

text: Algorithm

text: works

text: on

text: the

text: example

text: A

text: of

text: Figure

text: (bottom).

text: consists

text: of

text: the

text: following

text: sets:

text: and

text: which

text: ensure

text: the

text: overlap

text: relation

text: of

text: F

text: and

text: G,

text: which

text: ensure

text: the

text: overlap

text: relation

text: of

text: G

text: and

text: H,

text: and

text: which

text: ensure

text: the

text: overlap

text: relation

text: of

text: H

text: and

text: J.

text: Some

text: of

text: these

text: sets

text: are

text: redundant,

text: but

text: there

text: is

text: no

text: need

text: to

text: detect

text: this.

text: We

text: put

text: a

text: cardinality

text: counter

text: on

text: each

text: of

text: these

text: sets,

text: and

text: decrement

text: it

text: whenever

text: a

text: column

text: in

text: the

text: set

text: is

text: deleted.

text: At

text: least

text: one

text: column

text: from

text: each

text: of

text: these

text: sets

text: must

text: be

text: retained

text: to

text: maintain

text: the

text: connectivity

text: of

text: the

text: overlap

text: graph

text: of

text: C

text: Initially,

text: C

text: and

text: There

text: is

text: no

text: con-

text: Q

text: ﬁguration,

text: so

text: the

text: algorithm

text: retains

text: a

text: column

text: c

text: in

text: the

text: unconstrained

text: class

text: that

text: contains

text: a

text: in

text: row

text: Z.

text: Suppose

text: it

text: selects

text: c

text: It

text: eliminates

text: the

text: remaining

text: columns

text: and

text: of

text: the

text: unconstrained

text: class

text: from

text: C.

text: It

text: ﬁnds

text: the

text: conﬁgura-

text: tion

text: (c

text: c

text: c

text: The

text: ﬁrst

text: for

text: loop

text: eliminates

text: all

text: but

text: columns

text: is

text: skipped

text: because

text: it

text: is

text: a

text: member

text: of

text: the

text: unconstrained

text: Venn

text: class,

text: and

text: are

text: skipped

text: because

text: they

text: are

text: c

text: c

text: and

text: c

text: and

text: and

text: are

text: retained

text: because

text: they

text: are

text: A

text: the

text: only

text: remaining

text: elements

text: of

text: some

text: member

text: of

text: when

text: they

text: are

text: reached.

text: The

text: ﬁnal

text: for

text: loop

text: determines

text: that

text: elimination

text: of

text: or

text: would

text: undermine

text: all

text: conﬁgurations,

text: and

text: elimination

text: of

text: would

text: remove

text: the

text: last

text: remaining

text: element

text: A

text: of

text: the

text: member

text: of


text: 27 The resulting instance of a Tucker matrix is that depicted on the righthand side of Figure 9. That the algorithm is incomplete without the last two for loops is illustrated { } { } { } by the following example. Let R = c , c , R = c , c , c , R = c , c , { } 1 1 2 2 2 3 4 3 R4 5 Z = c , c , c , and (c , c , c , c , c ) be a consecutive-ones ordering of = { 1 2} 5 1 2 3 4 5 Q R , R , R . Let (c , c , c ) = (c , c , c ). None of the columns is removed 1 2 3 p(1) p(2) p(3) 1 3 5 bAy the ﬁrst for loop, since each of c2 and c4 is the sole element of a member of . However, c can be eliminated without undermining Lemma 15. Although p(2) A c , c , and c are in separate Venn classes, there is no member of p(1) p(2) p(3) that contains c and excludes both c and c . The second for loop is p(2) p(1) p(3) required to eliminate it. The third for loop handles analogous situations when (c , c , c ) is a 0-1-0 conﬁguration. p(1) p(2) p(3) Theorem 1. It takes O(size(M)) time to ﬁnd an instance of a Tucker subma- trix in any matrix that does not have the consecutive-ones property. Proof. The calls to TuckerRows, FindRows and FindColumns take O(size(M)) time by Lemmas 7, 13 and 20. This gives the result if TuckerRows returns a ≤ matrix with greater than four rows. If TuckerRows returns a matrix with i 4 rows, then we cannot use FindColumns to ﬁnd the columns of a Tucker subma- trix. However, by Lemma 6, every Tucker submatrix contains all i rows. One ≤ way to ﬁnd one is to generate all i! 24 = O(1) orderings of rows, and for each, to check for the existence of the column vectors of length i, as depicted in Figure 2. One of the matrices has been found if all of its depicted column vectors are found in one of the orderings. This takes O(m) = O(size(M)) time. 5 Finding a Lekkerkerker-Boland Subgraph { } An asteroidal triple (AT) in a graph G is a set of three vertices x, y, z such − − that there is a path from y to z in G N[x], a path from x to z in G N[y], and − a path from x to y in G N[z]. Lekkerkerker and Boland showed that a chordal graph is an interval graph if and only if it has no AT. The AT’s in the chordal LB subgraphs are those that are indicated by square vertices in Figure 3. In [9], an algorithm is given that ﬁnds an AT in a non-interval chordal graph in O(n + m) time. However, it does not follow from this result that there is a linear-time algorithm for ﬁnding an LB subgraph. One reason is that the algorithm of that paper can produce AT’s that are not the AT of any induced LB subgraph. Some of the diﬃculties posed by this and other pitfalls are explained below. Let M be the clique matrix of a graph G. For notational convenience, we will treat the rows of M as interchangeable with the corresponding vertices of G. This allows us to refer to the subgraph of G induced by a set X of rows of M, for example. Since G is the intersection graph of the rows of its clique matrix, G[X] is the intersection graph of the rows in X. We will also treat the columns

text: The

text: resulting

text: instance

text: of

text: a

text: Tucker

text: matrix

text: is

text: that

text: depicted

text: on

text: the

text: righthand

text: side

text: of

text: Figure

text: That

text: the

text: algorithm

text: is

text: incomplete

text: without

text: the

text: last

text: two

text: for

text: loops

text: is

text: illustrated

text: by

text: the

text: following

text: example.

text: Let

text: R

text: c

text: c

text: R

text: c

text: c

text: c

text: R

text: c

text: c

text: Z

text: c

text: c

text: c

text: and

text: (c

text: c

text: c

text: c

text: c

text: be

text: a

text: consecutive-ones

text: ordering

text: of

text: Q

text: R

text: R

text: R

text: Let

text: (c

text: c

text: c

text: (c

text: c

text: c

text: of

text: the

text: columns

text: is

text: removed

text: bAy

text: the

text: ﬁrst

text: for

text: loop,

text: since

text: each

text: of

text: and

text: is

text: the

text: sole

text: element

text: of

text: a

text: member

text: of

text: However,

text: c

text: can

text: be

text: eliminated

text: without

text: undermining

text: Lemma

text: Although

text: A

text: c

text: c

text: and

text: c

text: are

text: in

text: separate

text: Venn

text: classes,

text: there

text: is

text: no

text: member

text: of

text: that

text: contains

text: c

text: and

text: excludes

text: both

text: c

text: and

text: c

text: The

text: second

text: for

text: loop

text: is

text: required

text: to

text: eliminate

text: it.

text: The

text: third

text: for

text: loop

text: handles

text: analogous

text: situations

text: when

text: (c

text: c

text: c

text: is

text: a

text: conﬁguration.

text: Theorem

text: It

text: takes

text: O(size(M))

text: time

text: to

text: ﬁnd

text: an

text: instance

text: of

text: a

text: Tucker

text: subma-

text: trix

text: in

text: any

text: matrix

text: that

text: does

text: not

text: have

text: the

text: consecutive-ones

text: property.

text: Proof.

text: The

text: calls

text: to

text: TuckerRows,

text: FindRows

text: and

text: FindColumns

text: take

text: O(size(M))

text: time

text: by

text: Lemmas

text: and

text: This

text: gives

text: the

text: result

text: if

text: TuckerRows

text: returns

text: a

text: matrix

text: with

text: greater

text: than

text: four

text: rows.

text: If

text: TuckerRows

text: returns

text: a

text: matrix

text: with

text: i

text: rows,

text: then

text: we

text: cannot

text: use

text: FindColumns

text: to

text: ﬁnd

text: the

text: columns

text: of

text: a

text: Tucker

text: subma-

text: trix.

text: However,

text: by

text: Lemma

text: every

text: Tucker

text: submatrix

text: contains

text: all

text: i

text: rows.

text: One

text: way

text: to

text: ﬁnd

text: one

text: is

text: to

text: generate

text: all

text: i!

text: orderings

text: of

text: rows,

text: and

text: for

text: each,

text: to

text: check

text: for

text: the

text: existence

text: of

text: the

text: column

text: vectors

text: of

text: length

text: i,

text: as

text: depicted

text: in

text: Figure

text: One

text: of

text: the

text: matrices

text: has

text: been

text: found

text: if

text: all

text: of

text: its

text: depicted

text: column

text: vectors

text: are

text: found

text: in

text: one

text: of

text: the

text: orderings.

text: This

text: takes

text: O(m)

text: O(size(M))

text: time.

text: Finding

text: a

text: Lekkerkerker-Boland

text: Subgraph

text: An

text: asteroidal

text: triple

text: (AT)

text: in

text: a

text: graph

text: G

text: is

text: a

text: set

text: of

text: three

text: vertices

text: x,

text: y,

text: z

text: such

text: that

text: there

text: is

text: a

text: path

text: from

text: y

text: to

text: z

text: in

text: G

text: N[x],

text: a

text: path

text: from

text: x

text: to

text: z

text: in

text: G

text: N[y],

text: and

text: a

text: path

text: from

text: x

text: to

text: y

text: in

text: G

text: N[z].

text: Lekkerkerker

text: and

text: Boland

text: showed

text: that

text: a

text: chordal

text: graph

text: is

text: an

text: interval

text: graph

text: if

text: and

text: only

text: if

text: it

text: has

text: no

text: AT.

text: The

text: AT’s

text: in

text: the

text: chordal

text: LB

text: subgraphs

text: are

text: those

text: that

text: are

text: indicated

text: by

text: square

text: vertices

text: in

text: Figure

text: In

text: an

text: algorithm

text: is

text: given

text: that

text: ﬁnds

text: an

text: AT

text: in

text: a

text: non-interval

text: chordal

text: graph

text: in

text: O(n

text: m)

text: time.

text: However,

text: it

text: does

text: not

text: follow

text: from

text: this

text: result

text: that

text: there

text: is

text: a

text: linear-time

text: algorithm

text: for

text: ﬁnding

text: an

text: LB

text: subgraph.

text: One

text: reason

text: is

text: that

text: the

text: algorithm

text: of

text: that

text: paper

text: can

text: produce

text: AT’s

text: that

text: are

text: not

text: the

text: AT

text: of

text: any

text: induced

text: LB

text: subgraph.

text: Some

text: of

text: the

text: diﬃculties

text: posed

text: by

text: this

text: and

text: other

text: pitfalls

text: are

text: explained

text: below.

text: Let

text: M

text: be

text: the

text: clique

text: matrix

text: of

text: a

text: graph

text: G.

text: For

text: notational

text: convenience,

text: we

text: will

text: treat

text: the

text: rows

text: of

text: M

text: as

text: interchangeable

text: with

text: the

text: corresponding

text: vertices

text: of

text: G.

text: This

text: allows

text: us

text: to

text: refer

text: to

text: the

text: subgraph

text: of

text: G

text: induced

text: by

text: a

text: set

text: X

text: of

text: rows

text: of

text: M,

text: for

text: example.

text: Since

text: G

text: is

text: the

text: intersection

text: graph

text: of

text: the

text: rows

text: of

text: its

text: clique

text: matrix,

text: G[X]

text: is

text: the

text: intersection

text: graph

text: of

text: the

text: rows

text: in

text: X.

text: We

text: will

text: also

text: treat

text: the

text: columns