Anna Bernasconi
email: annab@di.unipi.it

On a hierarchy of Boolean functions hard to compute in constant depth †

Keywords: Boolean functions, AC 0 circuits, size complexity, harmonic analysis

Any attempt to find connections between mathematical properties and complexity has a strong relevance to the field of Complexity Theory. This is due to the lack of mathematical techniques to prove lower bounds for general models of computation.

This work represents a step in this direction: we define a combinatorial property that makes Boolean functions "hard" to compute in constant depth and show how the harmonic analysis on the hypercube can be applied to derive new lower bounds on the size complexity of previously unclassified Boolean functions.

Introduction

Any attempt to find connections between mathematical properties of functions and their computational complexity has a strong relevance to theory of computation. Indeed, there is the hope that developing new mathematical techniques could lead to discovering properties that might be responsible for lower bounds. The subject of this paper is related to the above general arguments, and in particular to showing how the Abstract Harmonic Analysis on the hypercube can provide some insight in our current understanding of Boolean function complexity. Our main result consists of new lower bounds on the size complexity of explicit functions, exactly derived by applying the above techniques.

One of the best-known results in Circuit Complexity is that constant depth circuits require exponential size to compute the parity function (see [4, 5, 11]). Here we generalize this result to a new hierarchy of functions.

This hierarchy is defined as follows. Let p be a positive rational number, 0 < p ≤ 1, and let B (p) n be the class of functions, depending on n variables, that take the value 1 with probability p, i.e. on exactly 2 n p input strings.

We then divide B (p) n into levels, where the k-th level, which we denote by B (p, k) , is defined as the subset of the functions f ∈ B (p) n such that any subfunction of f , depending on k (k ≥ log 1 p ) variables, takes the value 1 again with probability p, i.e. on 2 k p input strings (w.l.o.g. let us assume that 2 k p is an integer). These definitions are made precise below.

Our main result is that AC 0 -circuits cannot compute functions in the k-th level of B (p) n , whenever k = n -(log n) ω [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] and p = Ω(2 -polylog n ) .

More precisely, we prove that a circuit of constant depth d require size k) , for any p and any k.

Ω 2 (n-k) 1/d 20 p to compute any function in B (p,
We also prove that nontrivial functions exist for each level of this hierarchy if

k > log p + 1 log p n ,
and conjecture that this bound is not far from being asymptotically optimal.

The main tool of the lower bound proof is the harmonic analysis on the hypercube, that yields an interesting spectral characterization of the functions in the above hierarchy, together with a result proved in [8], stating that AC 0 functions have almost all of their power spectrum on the low-order coefficients.

Finally, notice that this paper generalizes results in [1], where it has been proven that AC 0 -circuits cannot compute strongly balanced functions. Indeed, the class of strongly balanced functions coincides with the n -(log n) ω(1) -th level of the class B (1/2) n .

The results presented in this paper have recently been improved in [3, 2], where it is shown how this spectral technique for proving lower bounds on the size-complexity of Boolean functions can be generalized in order to be applied also to functions which present the combinatorial structure described above only in an "approximate sense". In this way some new interesting lower bounds have been obtained for functions related to some arithmetic properties of integers. Precisely it has been shown that deciding if a given integer is square-free and testing co-primality of two integers by unbounded fan-in circuits of bounded depth requires superpolynomial size (the number theoretic counterpart of the spectral technique is a sieve method).

The rest of the paper is organized as follows. In Section 2 we provide some of the notation we use, and recall some basic definitions. In Section 3 we give the necessary background on Fourier transform on the hypercube, and review the results by Linial et al. [8] about the spectral characterization of AC 0 functions. Section 4 is devoted to the definition of the classes B (p) n and of their levels B (p, k) . In Section 5 we derive a spectral characterization of the functions in any level of B (p) n , and in Section 6 we prove our main result stating that AC 0 -circuits cannot compute functions in the level B (p, k) , whenever k = n -(log n) ω [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] and p = Ω(2 -polylog n ). In Section 7 we prove that nontrivial functions do exist in any level B (p, k) such that k > log p+1 log p n. Finally, in Section 8 we provide a framework for future research.

Basic Definitions

First of all, we provide some of the notation we use.

Given a Boolean function f on n binary variables, we will use different kinds of notation: the classical notation, where the input string is given by n binary variables; the set notation, based on the correspondence between the set {0, 1} n and the power set of {1, 2, . . . , n}; the 2 n -tuple vector representation f = ( f 0 f 1 . . . f 2 n -1 ), where f i = f (x(i)) and x(i) is the binary expansion of i. Unless otherwise specified, the indexing of vectors and matrices starts from 0 rather than 1.

We will use the notation | f | to denote the cardinality of f , that is the number of strings accepted by f :

| f | = |{w ∈ {0, 1} n | f (w) = 1}| .
Given a binary string w ∈ {0, 1} n , we denote with w (i) the string obtained from w by flipping its i-th bit (1 ≤ i ≤ n), i.e. w and w (i) differ only on the i-th bit, and by |w| 1 the hamming weight of w, i.e. the number of ones in it. If w and v are two binary strings of the same length, then w ⊕ v denotes the string obtained by computing the exclusive or of the bits of w and v. Finally, all the logarithms are to the base 2, and the notation polylog n stands for a function growing like a polynomial in the logarithm of n. We now review some basic definitions.

AC 0 circuits

An AC 0 circuit consists of AND, OR and NOT gates, with inputs x 1 , . . . , x n . Fan-in to the gates is unbounded. The size of the circuit (i.e. the number of the gates) is bounded by a polynomial in n, and its depth is bounded by a constant. Without loss of generality we can assume that negations occur only as negated input variables. If negations appear higher up in the circuit we can move them down to the inputs using De Morgan's laws which at most doubles the size of the circuit. Finally, observe that we have alternating levels of AND and OR gates, since two adjacent gates of the same type can be collapsed into one gate (for a more detailed description, see [5]).

Restriction

A restriction ρ is a mapping of the input variables to the set {0, 1, ⋆}, where ρ(x i ) = 0 means that we substitute the value 0 for x i ; -ρ(x i ) = 1 means that we substitute the value 1 for x i ; -ρ(x i ) = ⋆ means that x i remains a variable.

Given a function f on n binary variables, we will denote by f ρ the function obtained from f by applying the restriction ρ; f ρ will be a function of the variables x i for which ρ(x i ) = ⋆.

The domain of a restriction ρ, dom(ρ), is the set of variables mapped to 0 or 1 by ρ. The size of a restriction ρ, size(ρ), is defined as the number of variables which were given the value ⋆, i.e. size(ρ) = n -|dom(ρ)|.

Abstract Harmonic Analysis and AC 0 Functions

We give some background on abstract harmonic analysis on the hypercube. We refer to [7] for a more detailed exposition.

We consider Boolean functions as embedded in the space F of all real-valued functions on the domain {0, 1} n . On F we consider the standard scalar product

f , g = 1 2 n ∑ w∈{0,1} n f (w)g(w) (1)
with induced norm f = f , f 1/2 .
The functions Q w (x) = (-1) w 1 x 1 (-1) w 2 x 2 . . . (-1) w n x n = (-1) w T x are known as Fourier transform kernel functions, and the set

{Q w | w ∈ {0, 1} n }
is an orthogonal basis for F .

We can now define the Abstract Fourier Transform of a Boolean function f as the rational valued function f which defines the coordinates of f with respect to the basis

{Q w (x) | w ∈ {0, 1} n }, i.e., f (w) = 1 2 n ∑ x Q w (x) f (x) . (2)
Then

f (x) = ∑ w Q w (x) f (w) (3)
is the Fourier expansion of f . It is interesting to note that the zero-order Fourier coefficient is equal to the probability that the function takes the value 1, while the other Fourier coefficients measure the correlation between the function and the parity of subsets of its input bits. This is immediate to see if the Boolean functions are defined as mapping from {0, 1} n to {1, -1}, where -1 stands for "accept" and 1 stands for "reject" (see [8] for more details), but remains of course true even for {0, 1}-valued functions (the coefficients of order greater than zero differ in the two cases only by a constant factor).

Using the binary 2 n -tuple representation for the functions f and f , and considering the natural ordering of the n-tuples x and w, one can derive a convenient matrix formulation for the transform pair. Let us consider a 2 n × 2 n matrix H n whose (i, j)-th entry h i j satisfies h i j = (-1) x(i) T x ( j) , where x(i) T x( j) denotes the inner product of the binary expansions of i and j.

If f = [ f 0 f 1 . . . f 2 n -1 ] T and f = f0 f1 . . . f2 n -1 T , then, from the fact that H -1 n = 2 -n H n , we get f = H n f (4) and f = 1 2 n H n f . (5)
Note that the matrix H n is the Hadamard symmetric transform matrix and can be recursively defined as

H 1 = 1 1 1 -1 , H n = H n-1 H n-1 H n-1 -H n-1 . (6)
We now present an interesting application of harmonic analysis to circuit complexity, due to Linial et al. [8].

As we have already mentioned, one of the best known results in circuit complexity is that AC 0 circuits require exponential size to compute the parity function. More precisely, AC 0 -circuits cannot even approximate the parity function. This fact has a direct consequence on the Fourier transform, because, as we have already mentioned, the Fourier coefficients measure the correlation between the function and the parity of subsets of its input bits. Consequently, each high order Fourier coefficient of an AC 0 function must be very small (where "high order" means coefficients corresponding to strings of large cardinality). By exploiting this fact, Linial et al. were able to prove that not only is each individual high order coefficient small, but in fact the sum of squares (i.e. the power spectrum) associated with all high Fourier coefficients is very small.

Lemma 1 (Spectral lemma [8]) Let f be a Boolean function on n variables computable by a Boolean circuit of depth d and size M, and let θ be any integer. Then

∑ |w| 1 >θ ( f (w)) 2 ≤ 1 2 M 2 -θ 1/d 20 . (7)
⊓ ⊔

4 The Classes B (p) n and their Levels B (p, k) .

In this section we define classes of functions which generalize the notion of k-balanced functions introduced in [1]. Let p be a positive rational number, 0 < p ≤ 1.

Definition 1 (Class B (p) n ) B (p)
n is the class of Boolean functions depending on n variables that take the value 1 with probability p, i.e. on exactly 2 n p input strings.

Making use of the notion of restriction (see Section 2), we organize the functions in each class B (p) n into a sequence of levels. Let k be a positive integer such that log [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] p ≤ k ≤ n , and let us assume that 2 k p takes an integer value.

Definition 2 (k-th level of B

(p) n ) B (p, k) is the subset of B (p)
n consisting of all functions f such that, for any restriction ρ of size k, f ρ ∈ B (p) k .

We call B (p, k) the k-th level of B (p) n . In other words, B (p, k) consists of all functions f which take the value 1 with probability p, such that any subfunction f ρ depending on k variables, takes the value 1 again with probability p.

We now state some basic properties of the hierarchy of levels B (p, k) . Let k be a positive integer, such that log [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] p ≤ k ≤ n. Then.

• B (p, k) ⊆ B (p, k+1) . • B (p, n) = B (p)
n .

• The classes of k-balanced functions defined in [1] correspond to the k-th level of B (1/2) n .

• The parity function and its complement are the only two functions which belong to the first level of [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] .

B (1/2) n , i.e. to B (1/2,
The first two properties follow immediately from the definition of the hierarchy; for the last two, we refer the reader to [1]. In Section 7 we will prove that, for any p, B (p, k) is strictly contained in B (p, k+1) and that the levels B (p, k) are not empty, provided that

k > log p + 1 log p n . ( 8
)
Notice that, in the special case p = 1/2, it turns out that

B (1/2, k) ⊂ B (1/2, k+1) (9)
and that the levels B (1/2, k) are not empty, for any value of k, 1 ≤ k ≤ n (see [1] for more details). All these proofs will make use of the spectral characterization of these functions, which we derive in the following section.

Spectral Characterization of the Hierarchy of B (p) n Functions

We now derive a spectral characterization of the functions in any level of the class B (p) n . We denote by f0 the zero-order Fourier coefficient.

Theorem 2 (Spectral characterization)

A Boolean function f : {0, 1} n → {0, 1} belongs to the k-th level of the class B (p) n if and only if the following property holds:

(1) f ∈ B (p) n ;
(2) for any string w such that 0

< |w| 1 ≤ n -k, f (w) = 0.

Proof

• We start by proving the "only if" side of the theorem. Let f ∈ B (p) n and µ ≡ (µ 1 , µ 2 , . . . , µ n ) be a Boolean string such that 0

< |µ| 1 = n -ℓ ≤ n -k . Moreover, let U = {i | µ i = 1} .
For any string u ∈ {0, 1} n-ℓ , let f u denote the subfunction defined by the restriction that assigns to the variables x i such that i ∈ U, the (n -ℓ) values taken from the string u, and leaves undetermined the other ℓ variables.

Then, we have

f (µ) = 1 2 n ∑ w (-1) µ T w f (w) = 1 2 n ∑ w (-1) ∑ i∈U w i f (w) = 1 2 n ∑ u∈{0,1} n-ℓ   (-1) |u| 1 ∑ v∈{0,1} ℓ f u (v)   = 1 2 n ∑ u∈{0,1} n-ℓ (-1) |u| 1 | f u | .
For any u ∈ {0, 1} n-ℓ , the subfunction f u depends on ℓ ≥ k variables and, since f ∈ B (p, k) , and

B (p, k) ⊆ B (p, ℓ) for any ℓ ≥ k, we have f u ∈ B (p) ℓ and | f u | = 2 ℓ p. Thus, we get f (µ) = 2 ℓ p 2 n ∑ u∈{0,1} n-ℓ (-1) |u| 1 = 0 .
• We now prove the "if" side of the theorem, i.e., if properties (1) and ( 2) hold, then f ∈ B (p, k) .

Let us choose (nk) variables out of n, and let U be the set of the indices of these (nk) variables.

For any u ∈ {0, 1} n-k , let f u denote the subfunction obtained from f by assigning to the variables in the set U, the (nk) values taken from the string u, and leaving undetermined the other k variables.

For any u, f u depends on k variables. We show that any such subfunction takes the value 1 with probability p.

Let f # denote a vector whose entries are given by the cardinality of the 2 n-k subfunctions f u , and let fU denote a vector whose entries are the Fourier coefficients related to the 2 n-k strings w ≡ (w 1 , w 2 , . . . , w n ) such that w i = 0 for any i ∈ U. Note that all the 2 n-k coefficients in the vector fU are of order less than or equal to nk. Because of the recursive definition of Hadamard matrices, it turns out that fU = 1 2 n H n-k f # . From property (2) and from the fact that the zero order Fourier coefficient is equal to the probability that the function takes the value 1, it then follows

fU = p      1 0 . . . 0      , from which f # = 2 n H -1 n-k fU = 2 n 2 n-k H n-k fU = 2 k p H n-k      1 0 . . . 0      = 2 k p      1 1 . . . 1      .
Thus, the theorem follows by repeating the same argument for all the n k choices of the set U. ⊓ ⊔ 6 A Lower Bound on the Size Complexity of B (p) n Functions

We are now able to prove our main result, i.e., that AC 0 -circuits cannot compute functions in the k-th level of B (p) n , whenever k = n -(log n) ω [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] and p = Ω(2 -polylog n ) .

We first make use of the spectral characterization derived in Theorem 2, together with Lemma 1, to determine a lower bound on the size required by a depth d circuit to compute functions in the k-th level of B (p) n . Finally, an easy application of this bound will provide our thesis. In the following we will assume that p ≤ 1 2 (if p > 1 2 we can consider the function ¬ f which has the same size complexity as f ).

Theorem 3 (Size complexity)

Let f ∈ B (p, k) , p ≤ 1 2 , be a Boolean function depending on n variables, computable by a circuit of constant depth d and size M. Then M ≥ 2

(n-k) 1/d 20 p . ( 10
)
Proof An application of Lemma 1 yields the following inequality:

M ≥ 2 θ 1/d 20 2 ∑ |w| 1 >θ ( f (w)) 2 .
Let us choose θ = nk. From the fact that f (w) = 0 for any 0

< |w| 1 ≤ n -k (see Theorem 2) it follows that ∑ |w| 1 >n-k ( f (w)) 2 = ∑ w:|w| 1 =0 ( f (w)) 2 = ∑ w ( f (w)) 2 -( f0 ) 2 ,
where f0 denotes the zero-order Fourier coefficient. Then, by using the Parseval's identity

∑ v ( f (v)) 2 = f0 = p , we get ∑ |w| 1 >n-k ( f (w)) 2 = p -p 2 ≥ p 2 ,
and the thesis immediately follows:

M ≥ 2 (n-k) 1/d 20 2 ∑ |w| 1 >n-k ( f (w)) 2 = 2 (n-k) 1/d 20 p .

⊓ ⊔

Notice how this result establishes a clear connection between complexity and combinatorial properties of Boolean functions.

Our main result, stating that AC 0 -circuits cannot compute functions in the k-th level of B (p) n , whenever

k = n -(log n) ω(1) , (11)
and

p = Ω(2 -polylog n ) , (12)
follows immediately as a corollary of Theorem 3.

From the definition of f , and from the structure of Hadamard matrices, it turns out that the spectrum of f can be defined in terms of the spectrum of g, in the following way:

f (αβ) = 1 2 ĝ(β) if α = 0 -1 2 ĝ(β) if α = 1 .
If we now use the fact that g ∈ B (2 -t , t-1 t (n-1)+1) , together with the spectral characterization of Theorem 2, we obtain that f (w) = 0, whenever |w| 1 < n-1 t . In particular, we have that f (w) = 0 whenever |w| 1 < ⌊ n t+1 ⌋, and from Theorem 2 it follows that f ∈ B (2 -(t+1) , k) for k > t t+1 n, which completes our induction.

⊓ ⊔

Notice that, because of its construction, the function f defined in the proof of the above theorem is nondegenerated, i.e. it depends on all input variables. By defining f in a more complicated way it is possible, in some cases, to decrease the bound on k, but only by a constant factor. Therefore, we conjecture that the bound on k given in Theorem 6 is not far from being asymptotically optimal. Theorem 6 is an interesting result for the following two reasons. First of all, it allows us to verify that the classes of functions under investigation are not empty, at least for a significant number of levels. Moreover, since for constant values of the probability p, the functions in the deepest levels of the hierarchy can be regarded as "generalizations" of the parity function, it is interesting to understand how "deep" we can go in such a generalization, i.e. how close the combinatorial structure of level k functions is to the combinatorial structure of parity.

We now prove that, for p = 2 -t , B (2 -t , k) is strictly contained in B (2 -t , k+1) , provided that k > t-1 t n.

In other words, we prove that nontrivial examples of functions do exist for those levels of B (2 -t )

n
where k > t-1 t n. Theorem 7 Let p = 2 -t . If k > t-1 t n, then B (2 -t , k) is strictly contained in B (2 -t , k+1) . Proof The proof of the theorem is easily derived from that of Theorem 6. For t = 1, B (1/2, k) is strictly contained in B (1/2, k+1) for any k ≥ 1 (see [1]).

Let g be a Boolean function, depending on n -1 variables, which belongs to B (2 -t , k) but not to B (2 -t , k-1) , for k = nt t+1 > t-1 t (n -1). Then, the induction step can easily be proved by considering a function f defined as in the proof of Theorem 6.

⊓ ⊔

Conclusion

Any attempt to find connections between mathematical properties and complexity has a strong relevance to the field of Complexity Theory. This is due to the lack of mathematical techniques to prove lower bounds for general models of computation. This work represents a step in this direction: we define a combinatorial property that makes Boolean functions "hard" to compute in constant depth and show how the Fourier transform could be used as a mathematical tool for the analysis of Boolean functions complexity. Further work to be done includes a deeper analysis of the structure of the levels B (p, k) , in order to get an optimal lower bound on k, and, more in general, a deeper analysis of the connections between combinatorial properties, spectral properties and complexity of Boolean functions.

Corollary 4 Any function f ∈ B (Ω(2 -polylog n ), n-(log n) ω [START_REF] Bernasconi | On the complexity of balanced Boolean functions[END_REF] ) requires superpolynomial size to be computed by a constant depth circuit.

Proof Easily follows from Theorem 3.

⊓ ⊔

Note how the lower bound to the size can become exponential:

Corollary 5 Constant depth circuits require exponential size to compute functions in levels B (p, k) whenever k is s.t. nk = Ω(n ε ), for any positive constant ε < 1, and p = Ω(2 -polylog n ).

Proof Immediate from Theorem 3. ⊓ ⊔

7 Properties of the Hierarchy B (p)

In this section we prove that nontrivial functions do exist in the levels of the hierarchy B (p) n . More precisely, we assume that p = 1 2 t , where t = t(n) is an integer, and, by applying the spectral characterization derived in Section 5, we prove that B (p, k) is strictly contained in B (p, k+1) and that the sets B (p, k) are not empty, provided that

i.e. k > t-1 t n. Notice that, in the special case p = 1/2, i.e. t = 1, it turns out that

and that the levels B (1/2, k) are not empty, for any value of k, 1 ≤ k ≤ n (see [1] for more details).

Theorem 6

Let p = 1 2 t . For any n, B (2 -t , k) = / 0 if k > t-1 t n. Proof By induction on t.

Base

For any n, and for t = 1, the parity function and its complement belong to B (1/2, 1) and t-1 t n = 0.

Induction step

Let us suppose that, for any n, B (2 -t , k) = / 0 if k > t-1 t n. Let g be a Boolean function, depending on n-1 variables, which belongs to B (2 -t , k) for k = t-1 t (n-1) + 1 (to simplify the exposition, let us assume that t divides n -1).

We define f , depending on n variables, as follows:


C R Subramanian
email: crs@csa.iisc.ernet.in

Paths of specified length in a random k-partite graph

Keywords: random graphs, paths, bijections

Paths of specified length in random k-partite graphs

C.R.

Motivation

This problem arose in the analysis of algorithms for coloring random k-colorable graphs [START_REF] Subramanian | Improved Algorithms for Coloring Random Graphs[END_REF][START_REF] Subramanian | Algorithms for Coloring Random and Semi-Random Graphs[END_REF]. Consider a random graph drawn as explained in the abstract. To separate a color class, we fix a vertex x in the largest (or smallest) V i and and compute the number of l-paths (paths of length l), n(x, y, l), between x and an arbitrary vertex y. Depending on whether y belongs to the same class as x belongs to, the expectation of this quantity differs significantly. If we can show that n(x, y, l) is close to its expected value almost surely, this gives us a way of separating the class containing x. Repeating this k -2 times, one gets a k-coloring. The expectation of n(x, y, l) is N(x, y, l)p l , where N(x, y, l) is the total number of l-paths in the complete k-partite graph formed by V i s. The result stated in the abstract shows that the expectations differ significantly as required.

We do not discuss the algorithmic issues here since they have been outlined in [START_REF] Subramanian | Improved Algorithms for Coloring Random Graphs[END_REF]. We only prove the results stated in the abstract using only counting arguments. Even though the results are obviously true for bipartite graphs, for k ≥ 3, it is not so straightforward. We believe the arguments used here would be of interest to know. The basic idea is to partition (for each pair of start-end vertices) the corresponding set of l-paths into groups (based on the color classes of intermediate vertices). Then, for two different pairs, we establish an (almost) bijection between the corresponding groups. For any such mapped pair of groups, we also establish an (almost) bijection between the l-paths in them. This establishes the required statement.

2 Paths of specified length Definition 2.1 By an l-path between two vertices x and y, we mean a simple path of length l between x and y. A simple path is one in which no vertex appears more than once. An l-path is represented as a (l + 1)-tuple x, v 1 , . . . , v l-1 , y of vertices such that successive vertices in this sequence belong to different partite sets V i . ,y,l,i) denote the number of l-paths between x and y involving only vertices from W i . Given a tuple σ with integral component values and an integer j, c(σ, j) denotes the number of times j appears in σ.

Notations : G is a complete k-partite graph on the partite sets V 1 , . . . ,V k with each |V i | ≥ n/C for some constant C ≥ k. For each i, n i denotes the size |V i |. For each i, let W i =V i ∪ . . . ∪V k . For all i(1 ≤ i ≤ k -1), for all x ∈ V i , for all y ∈ W i such that y = x, let N(x
We obtain the following results.

Theorem 2.1 Assume that n 1 ≤ . . . ≤ n k . Let l be any fixed even integer ≥ 2. For all i,

1 ≤ i ≤ k -1, for all x, y ∈ V i , for all z ∈ W i -V i , we have N(x, z, l, i) = Θ(n l-1 ) if i ≤ k -2 N(x, y, l, i), N(x, y, l, i) -N(x, z, l, i) = Θ(n l-1 )
Proof: Consider any i(i = 1, . . . , k -1) and any x, y ∈ V i and z ∈ V r , r > i and fix these parameters. We use the factorial functions defined as follows : (n) 0 = 1. (n) l = n(n-1) . . . (n-l +1), l ≥ 1. Let P(x, y) denote the set of all l-paths between x and y involving only vertices from the ki + 1 partite sets V j (i ≤ j ≤ k). P(x, z) is defined similarly. That is, P(x, y) = { x, v 1 , . . . , v l-1 , y | the sequence is an l-path between x and y}. P(x, z) = { x, v 1 , . . . , v l-1 , z | the sequence is an l-path between x and z}.

Clearly, we have |P(x, y)| = O(n l-1 ) and |P(x, z)| = O(n l-1 ). Also if i = k -1, then there are only two partite sets, namely, V k-1 and V k and hence P(x, z) = / 0 and N(x, z, l, i) = 0. Define

B s l = { σ 1 , . . . , σ l-1 | σ 1 = i, σ l-1 = i, i ≤ σ j ≤ k, σ j = σ j+1 ∀ j} B d l = { σ 1 , . . . , σ l-1 | σ 1 = i, σ l-1 = r, i ≤ σ j ≤ k, σ j = σ j+1 ∀ j}
In the above, the superscript s (or d) is a short notation for the word "same" (or "different"). We have

|B s l |, |B d l | ≤ k l-1 . Now f : P(x, y) → B s
l is a mapping which identifies each l-path x, v 1 , . . . , v l-1 , y with the unique (l -1)tuple σ 1 , . . . , σ l-1 in B s l where if v m ∈ V j then σ m = j. Similarly, we can define a mapping g : P(x, z) → B d l which identifies each l-path in P(x, z) with a unique (l -1)-tuple in B d l . We use the elements of B s l ( or B d l ) to partition the set P(x, y) ( or P(x, z) ) as follows. P(x, y) = σ∈B s l P σ where P σ = {τ ∈ P(x, y) | f (τ) = σ}.

Clearly σ ∈ B s l, j . Also it can be verified that h j is a one-to-one and onto mapping. Since B s l, j and B d l, j are finite sets, it follows that |B s l, j | = |B d l, j |. Thus, we have |B s l | ≥ |B d l | + 1 and the first assertion is true. To prove the second assertion, define the mapping h : B d l → B s l to be as follows. For each τ ∈ B d l , define h(τ) = h j (τ) where j is such that τ ∈ B d l, j . Clearly, h is a one-to-one mapping since each h j is a one-to-one mapping. We prove that for each τ ∈ B d l , we have

|P h(τ) | ≥ |P τ |[1 -o(1)
]. Let τ ∈ B d l be any tuple and let σ denote the tuple h(τ). We know τ ∈ B d l, j for some j, 2 ≤ j ≤ l. If j = l, then we have σ = τ and hence

|P σ | ≥ |P τ |[1 -o(1)]. If j = l -2, l -4, . . . , 2, then clearly, c(τ, m) = c(σ, m) for all values of m (i ≤ m ≤ k) and hence |P σ | ≥ |P τ |[1 -o(1)]. If j = l -1, l -3, . . . , 3, then clearly, c(τ, m) = c(σ, m) for all values of m (i ≤ m ≤ k) such that m = i, m = r. Also, c(σ, r) = c(τ, r) + 1 and c(τ, i) = c(σ, i) + 1. Since n i ≤ n r (r > i) by assumption, we have |P σ | ≥ |P τ |[1 -o(1)].
Thus, we have

N(x, y, l, i) -N(x, z, l, i) = |P(x, y)| -P(x, z)| = | σ∈B s l P σ | -|
Thus,

N(x, y, l, i) -N(x, z, l, i) = Θ((n r ) l/2 (n i ) l/2-1 ) = Θ(n l-1 ) Hence, N(x, z, l, i) = Θ(n l-1 ) if i ≤ k -2 N(x, y, l, i), N(x, y, l, i) -N(x, z, l, i) = Θ(n l-1 ).
This completes the proof of the theorem.

Using similar arguments, we can prove the following theorem also. Theorem 2.2 Assume that n 1 ≥ . . . ≥ n k . Let l be any fixed odd integer ≥ 3. For all i (1 ≤ i ≤ k -1), for all x, y ∈ V i , for all z ∈ W i -V i , we have

N(x, y, l, i) = Θ(n l-1 ) if i ≤ k -2 N(x, z, l, i), N(x, z, l, i) -N(x, y, l, i) = Θ(n l-1 )
3 Conclusions

1.

The main result of the paper is that the number of l-paths joining a vertex x (in the largest or smallest V i depending on the parity of l) and a vertex y differs significantly depending on where y comes from. A close look at the proof (particularly, derivation of ( 1)) shows that this holds even if we allow k, l and C to vary with n, provided lk l C l = o(n). 2. It would be interesting to extend these results to structures other than simple paths. Such results can be applied to the design and analysis of efficient algorithms for random graphs (see [START_REF] Frieze | Algorithmic Theory of Random Graphs[END_REF] for a survey).

≥

  |P σ |o(|P σ |) where σ = r, i, . . . , r .

† Present address: The Institute of Mathematical Sciences, Taramani, Chennai -600 113, INDIA. email : crs@imsc.ernet.in 1365-8050 c 2001 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France

). The [1o(1)] factor arises not only because of factorials, but also because x, y and z have to be excluded from consideration.

Also B s l is non-empty and it contains at least one element, namely, the tuple r, i, r, i, . . . , r . Hence N(x, y, l, i) = |P(x, y)| = Θ(n l-1 ). Also, if i ≤ k -2, then there are at least 3 partite sets to be considered and hence

). In order to prove this, it is enough to prove that the following two assertions are true.

2. There exists a one-to-one mapping h :

We prove that the two assertions are true as follows. Now, partition B s l , B d l into

where

B s l,1 = { r, i, r, i, . . . , r } Now B d l,1 cannot be defined similarly since l is even. It is easy to see that the definitions form a welldefined partition of B s l and B d l . In other words, for each σ ∈ B s l , there exists a unique value of j between 1 and l such that σ ∈ B s l, j . Similarly, for each τ ∈ B d l , there exists a unique value of j between 2 and l such that τ ∈ B d l, j . Now we claim that for all j such that 2 ≤ j ≤ l, |B s l, j | = |B d l, j |. For j = l, this follows from B s l,l = B d l,l . For j < l, consider the mapping h j : B d l, j → B s l, j defined as follows. Let τ ∈ B d l, j be any tuple. Then, h j (τ) = σ where σ is defined as

• For all m such that j ≤ m ≤ l -1, σ m = i if τ m = r and σ m = r if τ m = i.


David W Krumme

Paraskevi Fragopoulou

Minimum Eccentricity Multicast Trees

Keywords: multicast, eccentricity, algorithm, communications, graph, network

We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the minimum eccentricity multicast tree problem, and is directly related to the quality of service requirements of real multipoint applications. We deal directly with the problem in its general form, meaning that the sets of source and sink nodes need not be overlapping nor disjoint. The main contribution of this work is a polynomial algorithm for this problem on general networks which is inspired by an innovative method that uses geometric relationships on the xy-plane.

Introduction

Multipoint applications are of growing importance in broadband communication networks and the Internet. In a multipoint application, a number of participants, remotely located, wish to exchange data for a duration of time. The simplest possible approach would be to have each dissemination take the form of a broadcast from the originator of the data to a set of receivers. This approach suffers from the overhead of setting up broadcast trees tailored to each use. An approach with less overhead is to construct a single tree to be used by varying sets of senders and receivers during the multipoint application. The price paid for this reduction in overhead is an increase in latencies and traffic concentration [2]. Shared trees have been built as either exact or approximate centered trees in which some distance measure from a single node is minimized [START_REF] Wall | Mechanisms for Broadcast and Selective Broadcast[END_REF]1]. Generally, minimizing sums of distances leads to NP-complete problems such as the Steiner tree problem [START_REF] Waxman | Routing of Multipoint Connections[END_REF], while minimizing worst-case distances leads to tractable problems. In this paper, we address the problem of minimizing worst-case latencies in a general setting.

The network is modeled by a weighted undirected graph. Nodes represent locations of possible participants and the weights on the edges represent packet communication delays. We formulate the problem as follows: at a certain time we assume that a number of the network nodes, identified as the participants of a multipoint application, wish to establish a communication so that the maximum delay between any pair of participants is minimized. We further assume that the participants of the group are either sources of information, either sinks (receivers), or both, meaning that the groups of source and sink nodes are neither overlapping, nor disjoint. Only pairs of source and sink nodes contribute to the maximum end-to-end delay.

This problem can be solved in polynomial time. McMahan and Proskurowski [START_REF] Mcmahan | Multi-source spanning trees: Algorithms for minimizing source eccentricities[END_REF] have independently established this via an O(|V | 3 + |E||V |log|V |) algorithm. We present an algorithm with running time O(|V | 3 + |E||V |) which provides a solution to the problem on general networks. Our algorithm returns a partial subtree of the network that includes at least all the participants of the multipoint group, such that the maximum distance between any source node and any sink node is the minimum possible.

The construction of spanning trees, or even partial spanning trees on graphs with respect to different constraints is an old problem and have been dealt with in different papers. Different measures of goodness have been studied under various restrictions for the network or the source and sink sets. In its general form, the construction of optimum communication spanning trees was initiated in [START_REF] Hu | Optimum Communication Spanning Trees[END_REF]. In this paper, the problem was defined on the complete graph with a length and a requirement on the edges. The cost measure that had to be minimized was the sum of vertex distances weighted by the requirements between all vertices of the network. By setting the requirements equal to zero and parameterizing the number of source nodes, the problem was treated in [3] and was shown to be NP-complete. Some exact solutions were provided for the 2-source problem on restricted classes of graphs, such as unicycles and cactuses. Furthermore, the optimal solution to the 2-source problem on general graphs was approximated within a factor of 2. In an other recent paper [START_REF] Wu | A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees[END_REF] an approximation algorithm was provided for the all source problem. In [START_REF] Rouskas | Multicast Routing with End-to-End Delay and Delay Variation Constraints[END_REF] some heuristic algorithms were given for the minimum partial spanning trees taking into consideration the delay between a single source node and a group of sink (destination) nodes, while trying to bound the maximum difference in these delays.

The problem treated in this paper was proposed in [3] in the more restricted form, where the sink nodes were all the nodes of the network and by parameterizing the number of source nodes only. In [3], a pseudopolynomial algorithm was provided for this restricted version of the problem, and the weights on the edges had to be bound by the size of the graph. The 2-source problem on general graphs was efficiently approximated by a factor of 2. In this paper, we treat this problem in a much more general form, where the number of sink nodes is also parameterized. Moreover, the sets of sources and sinks are neither overlapping nor disjoint. We provided an innovative polynomial algorithm on general graphs. This problem is related to the selection of a subset of vertices in the graph to minimize a given cost function, or to the selection of p-centers [5].

The remaining of this paper is organized as follows: In section 2, we give a formal definition of the problem. In section 3, we show that an equivalent problem is to find a subdivision of a single edge that yields a spanning tree that minimizes distances to the point of the cut. This makes it easy to construct a minimum-eccentricity spanning tree once the correct edge has been identified. In section 4, we establish formulas and properties that the algorithm depends upon. In section 5 the actual algorithm is presented in detail and its complexity is analyzed. We conclude in section 6 with some suggestions for further research.

Network model and problem definition

In what follows the terms vertex and node are used interchangeably. Similarly for the terms edge and link.

A network is modeled as an undirected weighted graph G = (V, E), where V is the set of network nodes and E is the set of edges. An edge connecting two nodes v 1 and v 2 , denoted by (v 1 , v 2 ), has an associated weight ℓ(v 1 , v 2 ), which is a nonnegative real number, and represents the delay that data packets experience on this edge.

Consider a multipoint application that requires a set of source nodes S 1 to transmit data to a set of sink (destination) nodes S 2 . In order for the communication to proceed, we need to establish paths between each pair of source/sink nodes. In general, and for efficiency reasons, multicast packets are routed through the links of a multicast tree that includes at least all nodes of S 1 ∪ S 2 . Nodes that do not belong in the multipoint application as sources or sinks can be used as relay nodes in the multicast tree. However, for obvious reasons, these nodes are never leaf nodes of the tree.

Let us suppose that T is the multicast tree of G used in a certain multipoint application with source nodes S 1 and sink nodes S 2 . The total communication delay between a source node v 1 and a sink node v 2 using T is denoted by d T (v 1 , v 2 ), which is the weighted distance between v 1 and v 2 in T . One objective that has to be taken into account during the construction of a multicast tree T is the maximum delay between any source and any sink node. This objective is directly related to the quality of service requirements of the multipoint application because packets delivered more than a certain number of time units later could be of no value to the receiver. The most desirable objective is to construct a multicast tree that minimizes the maximum source/sink delay. The maximum distance between any source and any sink node in a multicast tree is the eccentricity of this tree. More formally, we express the Minimum Eccentricity Multicast Tree problem as follows:

Problem: Given a network G = (V, E), a set of source nodes S 1 , a set of sink nodes S 2 , a link delay

ℓ(v 1 , v 2 ) for each edge (v 1 , v 2 )
. Assume that T is the set of all multicast trees of G that include at least the nodes S 1 ∪ S 2 . For each tree T ∈ T we define its eccentricity e(T ) = max

s 1 ∈S 1 ,s 2 ∈S 2 d T (s 1 , s 2 ) (1)
We wish to find the tree T ∈ T that has the minimum eccentricity e(G) = min

T ∈T e(T ) (2)
In this paper, we show that this problem is polynomial and we describe an efficient algorithm that constructs minimum eccentricity multicast trees on general networks.

Before we proceed to the description of the algorithms we need the following definitions and notation:

• For any subgraph H of G, d H (v 1 , v 2 )
is the weighted distance between v 1 and v 2 in H.

• If P is a path between v 1 and v 2 , then a vertex c of P is a midpoint if D P (v 1 , c) = D P (v 2 , c). • A minimum-distance spanning tree rooted at c is a spanning tree T in which d T (v, c) = d G (v, c) for all v ∈ V . • If T is a spanning tree, an S i -critical path (i = 1 or i = 2) is a path in T between v 1 ∈ S i and v 2 ∈ S i such that d T (v 1 , v 2 ) ≥ d T (v ′ 1 , v ′ 2 ) for all v ′ 1 ∈ S i and v ′ 2 ∈ S i . • A 1-refinement R of a weighted graph G is obtained by replacing an edge E R = (u, w) by two edges (u, c R ) and (w, c R ) where c R ∈ V is a new vertex, with ℓ(u, c R ) + ℓ(w, c R ) = ℓ(u, w). The resulting graph is denoted G R .
If T is a spanning tree of G that contains E R , then the 1-refinement can be viewed also as a 1-refinement T R of T .

• R is the set of all 1-refinements of G.

• For any 1-refinement R ∈ R , d(R) = max s∈S 1 d G R (s, c R ) + max s∈S 2 d G R (s, c R ) (3)
• d(G) = min R∈R d(R)
3 Characterizing the solutions

In this section we show that a minimum eccentricity multicast tree is a partial shortest path tree rooted at some "point" in the network that includes at least all source and sink nodes. This point could be either a vertex, in the ideal case, or a point c R lying on an edge, produced by an 1-refinement of the graph. This result will be used in the following section to derive a polynomial algorithm for this problem.

Lemma 1 Let R ∈ R . Let T be a minimum-distance spanning tree rooted at c R . Then e(T ) ≤ d(R).

Proof e(T ) = max

s 1 ∈S 1 ,s 2 ∈S 2 d T (s 1 , s 2 ) ≤ max s 1 ∈S 1 d T (s 1 , c R )) + max s 2 ∈S 2 d T (s 2 , c R ) ≤ max s 1 ∈S 1 d G (s 1 , c R )) + max s 2 ∈S 2 d G (s 2 , c R ) = d(R) ✷ Lemma 2 Let T ∈ T . Let R be a 1-refinement of T such that c R is the midpoint of some S i -critical path in T , for i = 1 or i = 2. Then d(R) ≤ e(T ).
Proof Assume w.l.o.g. that i = 1, and that the S i critical path connects s with s

′ . Let D = d T (s, c R ) = d T (s ′ , c R ).
Claim (1): For any

s 1 ∈ S 1 , d G (s 1 , c R ) ≤ D. If not, then d T (s 1 , s ′ ) ≥ d T (s 1 , c R ) + d T (c R , s ′ ) > 2D = d T (s, s ′ ) (4) if the path in T from s 1 to s ′ passes through c R or d T (s 1 , v) ≥ d T (s 1 , c R ) + d T (c R , s) > 2D = d T (s, s ′ ) (5)
if the path in T from s 1 to s passes through c R . Either case contradicts the assumption that the (s, s ′ )-path in T is an S 1 -critical path.

Claim (2):

For any s 2 ∈ S 2 , d G (s 2 , c R ) ≤ e(T ) -D. If not, then d T (s 2 , s ′ ) ≥ d T (s 2 , c R ) + d T (c R , s ′ ) > e(T ) (6)
if the path in T from s 2 to s ′ passes through c R or

d T (s 2 , s) ≥ d T (s 2 , c R ) + d T (c R , s) > e(T ) (7)
if the path in T from s 2 to s passes through c R . Either of these contradicts the definition of e(T ).

Combining claims ( 1) and ( 2)

yields d(R) ≤ D + (e(T ) -D) = e(T ). ✷ Theorem 1 d(G) = e(G).
Proof Let T be such that e(T ) = e(G) and let R ′ be a 1-refinement of T with c R ′ the midpoint of some

S i -critical path in T . By Lemma 2, d(R ′ ) ≤ e(T ). Thus d(G) ≤ d(R ′ ) ≤ e(T ) = e(G). Let R be such that d(R) = d(G) and let T ′ be a minimum-distance spanning tree rooted at c R . By Lemma 1, e(T ′ ) ≤ d(R). Thus e(G) ≤ e(T ′ ) ≤ d(R) = d(G). Combining these results yields d(G) = d(R ′ ) = e(G) = e(T ′ ). ✷
Based on the previous theorem, we provide an upper bound for eccentricity.

Corollary 1 e(G) ≤ 2 radius(G), where radius(G) = min c∈V max v∈V d G (c, v). Proof Let R ∈ R be determined by a vertex c R for which max v∈V d G (c R , v) = radius(G). Then e(G) = d(G) ≤ d(R) ≤ 2 radius(G). ✷
When an edge must be split into two nontrivial parts to obtain the minimum value of d(R), e(G) will be less than 2 radius(G). This is the case with the graph of Figure 2, where radius(G) = 25 (with w as center) and e(G) = 42 (with (u, w) split and ℓ(u, c R ) = 3 and ℓ(w, c R ) = 9).

The customary approach to forming a tree is to root it at a vertex of the given graph, rather than at a point created through the subdivision of an edge. The eccentricity of such a tree is bounded above by

d(G) = min v∈V max s∈S 1 d G (s, v) + max s∈S 2 d G (s, v) (8)
Theorem 1 allows us to determine in general that such a rooted tree is within one edge weight of being optimal:

Theorem 2 e(G) ≤ d(G) ≤ e(G) + max (u,w)∈E ℓ(u, w).
Proof The first inequality is a consequence of the definitions. For the second, let c R define a 1-refinement

R such that d(R) = d(G). Let the edge divided by c R be (u, w) where ℓ(u, c R ) ≤ ℓ(w, c R ).
Then by the triangle inequality, for all

v ∈ V , d G (u, v) ≤ ℓ(u, c R ) + d G R (v, c R )
, and thus for any

s 1 ∈ S 1 and s 2 ∈ S 2 , d G (s 1 , u) + d G (s 2 , u) ≤ d G R (s 1 , c R ) + d G R (s 2 , c R ) + 2ℓ(u, c R ). (9)
This implies d G (s

1 , u) + d G (s 2 , u) ≤ d(G) + ℓ(u, w). ✷ t L t t ε t ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ L -ε L ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ L -ε ε t L t
Fig. 1: The optimal edge-rooted tree has eccentricity 2L + 2ε. The optimal vertex-rooted tree has eccentricity 3L -ε.

The upper bound is tight, as the graph in Figure 1 illustrates, where S 1 comprises the two degree-1 vertices and S 2 the two degree-2 vertices. There are only eight possible spanning trees, so it is not difficult to find the optimal trees by exhaustive checking. The optimal vertex-rooted tree is rooted at one of the degree-4 vertices, uses at least one edge weighted L -ε, and has eccentricity 3L -ε. The optimal edge-rooted tree is based on bisecting the edge in the middle of the diagram, does not use either edge weighted L -ε, and has eccentricity 2L + 2ε.

Basis for an algorithm

The algorithm focuses on identifying the appropriate edge (u, w) that can be cut to create a "center" c R from which to construct a minimum-distance spanning tree. This edge is found by examining for each edge (u, w) the longest weighted distances from u and w to members of S 1 and S 2 . The constructions in this section will be illustrated using the example in Figure 2.

t p 1 t q 1 t r 1 t s 1 t u t w t p 2 t q 2 t r 2 6 12 ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ 13 ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ ◗ 11 ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ 11 17 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 7 12 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 18 25 23 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 21 16
12 14 For a given edge (u, w) and set S i , the fixed reference point (a uw i0 , b uw i0 ) is used, where

S 1 = {p 1 , q 1 , r 1 , s 1 } S 2 = {p 2 , q 2 , r 2 }
a uw i0 = max s∈S i d G (s, w) -ℓ(u, w) (11) b uw i0 = max s∈S i d G (s, u) -ℓ(u, w) (12)
In the example, (a uw 10 , b uw 10 ) = (6, 5). Denote by L uw i the union of all the closed rectangles determined by points in D uw i ; that is,

L uw i = (a,b)∈D uw i L (a uw i0 ,b uw i0 ) (a, b) (13)
Denote by Q uw i the complement of L uw i with respect to the upper-right quarter plane Q(a uw i0 , b uw i0 ), that is,

Q uw i = Q(a uw i0 , b uw i0 ) \ L uw i ( 14
)
Figure 3 illustrates these constructions in the case of the graph from Figure 1, for edge (u, w) and S 1 .

The points of D uw 1 are marked as p 1 , q 1 , r 1 , s 1 . Although it does not happen in this example, in general a uw i0 and/or b uw i0 may be negative, and some rectangles in D uw i may be empty. The rectangles for vertices at maximum distance from u or w are always nonempty.

The essential property of Q uw i is described in the following lemma.

Lemma 3 Q(a, b) ⊆ Q uw i if and only if for every vertex v ∈ S i , either d G (v, u) ≤ a or d G (v, w) ≤ b. Proof If d G (v, u) > a and d G (v, w) > b, then (d G (v, u), d G (v, w)) ∈ Q(a, b). But from the definition, (d G (v, u), d G (v, w)) ∈ L uw i . This is impossible since Q uw i L uw i = / 0. ✷
Since L uw i is the union of a finite number of closed rectangles all of which have (a uw i0 , b uw i0 ) as lower left corner, the region Q uw i is the union of a finite number of upper-right quarter planes. Let Q uw i be the collection of quarter planes Q(a, b) that are maximal in Q uw i . Clearly, Q uw i comprise a minimal finite set of upper-right quarter planes whose union is

Q uw i , and if Q(a, b) ⊆ Q uw i , then Q(a, b) is a subset of some member of Q uw i .
It is relatively easy to see from Figure 3 that for our example a minimal set of upper-right quarter planes whose union is Q uw 1 is the following

Q uw 1 = {Q(a 1 , b 1 ), Q(a 2 , b 2 ), Q(a 3 , b 3 )}. ( 15
)
An essential property of Q uw i is the following:

Lemma 4 Let Q(a, b) ∈ Q uw i . If a = a uw i0 and b = b uw i0 , then for some u ′ ∈ V , d G (u ′ , u) = a and d G (u ′ , w) > b,

and for some w

′ ∈ V , d G (w ′ , w) = b and d G (w ′ , u) > a. x y ✇ (a 0 , b 0 ) ✇ p 1 ✇ q 1 ✇ r 1 ✇ s 1 ✇ (a 1 , b 1 ) ✇ (a 2 , b 2 ) ✇ (a 3 , b 3 ) L uw 1 Q uw 1

Proof Consider all vertices u

′ for which d G (u ′ , w) > b. This set is nonempty because otherwise Q(a uw i0 , b) ⊆ Q uw i which is impossible because Q(a, b) is maximal and a = a uw i0 . For all such u ′ , d G (u ′ , u) ≤ a by Lemma 3. Now choose u ′ to maximize d G (u ′ , u). If then d G (u ′ , u) = a ′ < a, Q(a ′ , b) ⊆ Q uw i contradicting the max- imality of Q(a, b). Thus d G (u ′ , u) = a. The proof for w ′ is analogous. ✷ Let the members of Q uw i be Q(a uw i1 , b uw i1 ), Q(a uw i2 , b uw i2 ), . . . , Q(a uw iN uw i , b uw iN uw i ) (16) arranged so that a uw i1 < a uw i2 < • • • < a uw iN uw i . ( 17
)
Since no member of Q uw i can contain any other, all the values a uw ik are distinct, all the values b uw i j are distinct, and it must be the case that

b uw i1 > b uw i2 > • • • > b uw iN uw i . ( 18
)
Geometrically, these properties reflect that fact that the points (a uw ik , b uw ik ) are the lower-left-hand corners that occur on the boundary between L uw i and Q uw i . In our example (see Figure 3),

Q uw 1 = {Q(a 1 , b 1 ), Q(a 2 , b 2 ), Q(a 3 , b 3 )} = {Q(6, 13), Q(12, 7), Q(17, 5)} . ( 19
)
The lower-left-hand corners that occur on the boundary between L uw i and Q uw i have the property described in lemma 4. Intuitively, this property can be explained as follows: for a certain edge (u, w) of the graph and for a subset of nodes S 1 , a point (a uw 1k , b uw 1k ) means that the nodes of S 1 are at maximum distance a uw 1k from u or at maximum distance b uw 1k from w. Furthermore, there is at least one node at distance a uw 1k from u whose distance from w is at least b uw 1k , and the other way around (there is a node at distance b uw 1k from w whose distance from u is at least a uw 1k ). The algorithm is based on a linear scan of the values (a uw ik , b uw ik ). The following lemmas establish the properties that enable this.

Lemma 5

(a) a uw i1 = a uw i0 ;

(b) b uw i1 ≤ max v∈S i d G (v, w); (c) a uw iN uw i ≤ max v∈S i d G (v, u); (d) b uw iN uw i = b uw i0 . Proof (a) Obviously Q(a uw i0 , max v∈S i d G (v, w)) ⊆ Q uw i . Since a uw i0 ≤ a uw i1 < a uw i2 < • • • < a uw iN uw i , the member of Q uw i that contains Q(a uw i0 , max v∈S i d G (v, w)) must be Q(a uw i1 , b uw i1 ) and this implies a uw i1 = a uw i0 . (b) Let b ′ be the maximum of d G (v, w) for all vertices v such that d G (v, u) > a uw i0 . Then Q(a uw i0 , b ′ ) ⊆ Q uw i implies Q(a uw i0 , b ′ ) ⊆ Q(a uw i1 , b uw i1
) and thus b uw i1 ≤ b ′ which implies the result.

(c) and (d) are analogous to (a) and (b) respectively. ✷ Lemma 6 For any (u, w), i ∈ {1, 2}, and 0 ≤ k ≤ N uw i , a uw ikb uw ik ≤ ℓ(u, w). Proof By symmetry, assume that b uw ik ≥ a uw ik . For k = 0, the result follows from the definitions and the fact that a path to u or w can be extended using the edge (u, w).

For k = 1, Lemma 5 implies

b uw i1 -a uw i1 ≤ max v∈S i d G (v, w) -a uw i0 = ℓ(u, w). ( 20
) For k = N uw i , b uw iN uw i -a uw iN uw i ≤ b uw i0 -a uw i0 ≤ ℓ(u, w), (21)
by Lemma 5 and the fact that a uw ik is an increasing function of k.

For 1 < k < N uw i , suppose by way of contradiction that b uw ik -a uw ik > ℓ(u, w). Let u ′ be as in Lemma 4. Then d G (u ′ , w) -d G (u ′ , u) ≥ b uw ik -a uw ik > ℓ(u, w) (22)
contradicting the existence of a path from u ′ through u to w of length d G (u ′ , u) + ℓ(u, w). ✷ Lemma 7 Let (u, w) be any edge and let 1 ≤ k ≤ N uw 1 and 1 ≤ j ≤ N uw 2 . Then there exists a spanning tree T such that e(T ) ≤ max(a uw 1k + ℓ(u, w) + b uw 2 j , a uw

2 j + ℓ(u, w) + b uw 1k ) (23)
-a = b uw 1k -a uw 1k . Since Q(a, b) ⊆ Q uw 2 , d G (v, u) ≤ a or d G (v, w) ≤ b for every v ∈ S 2 .
Let the 1-refinement R be determined by replacing (u, w) with (u, c R ) and (w, c R ), where

ℓ(u, c R ) = 1 2 ℓ(u, w) - 1 2 (a uw 1k -b uw 1k ) ℓ(w, c R ) = 1 2 ℓ(u, w) + 1 2 (a uw 1k -b uw 1k ) (24)
Note that Lemma 6 ensures that ℓ(u, c R ) and ℓ(w, c R ) are nonnegative.

Let s ∈ S 1 . If d G (s, u) ≤ a uw 1k , then d G R (s, c R ) ≤ d G (s, u) + d G R (u, c R ) ≤ 1 2 ℓ(u, w) + 1 2 a uw 1k + 1 2 b uw 1k . (25)
Otherwise, d G (s, w) ≤ b uw 1k which yields

d G R (s, c R ) ≤ d G (s, w) + d G R (w, c R ) ≤ 1 2 ℓ(u, w) + 1 2 a uw 1k + 1 2 b uw 1k . (26)
Similarly, for v ∈ S 2 , if d G (v, u) ≤ a, then d G R (v, c R ) ≤ d G (v, u) + d G R (u, c R ) ≤ a + 1 2 ℓ(u, w) + 1 2 (b uw 1k -a uw 1k ) (27) = a + 1 2 ℓ(u, w) + 1 2 (b -a). Otherwise, d G (v, w) ≤ b, so that d G R (v, c R ) ≤ d G (v, w) + d G R (w, c R ) ≤ b + 1 2 ℓ(u, w) - 1 2 (b uw 1k -a uw 1k ) (28)
= b + 1 2 ℓ(u, w) - 1 2 (b -a).
Combining these results gives

d(R) ≤ 1 2 (a uw 1k + b uw 1k ) + ℓ(u, w) + 1 2 (a + b) (29) = ℓ(u, w) + a uw 1k + b uw 1k + λ.
The boundary of Q uw 2 is such that for (a, b) and (a uw 2 j , b uw 2 j ), as for any two points on the boundary, if

a uw 2 j < a, then b uw 2 j ≥ b. If a uw 2 j ≥ a, then a uw 1k + λ ≤ a uw 2 j and d(R) ≤ ℓ(u, w) + a uw 2 j + b uw 1k . Otherwise, b uw 2 j ≥ b, so that b uw 1k + λ ≤ b uw 2 j and d(R) ≤ ℓ(u, w) + a uw 1k + b uw 2 j . Thus d(R) ≤ max(a uw 1k + ℓ(u, w) + b uw 2 j , a uw 2 j + ℓ(u, w) + b uw 1k ). (30)
The result now follows from Lemma 1. ✷ Lemma 8 Let T be a minimum-eccentricity spanning tree. Let u ′ , w ′ be the endpoints of any S i -critical path in T , and let (u, w) be an edge in that path such that d T (u ′ , u) ≤

d G (v, u) ≤ d G (u 1 , u) ≤ d T (u 1 , u) (32) or d G (v, w) ≤ d G (w 1 , w) ≤ d T (w 1 , w). ( 33
)
This means that

Q(d T (u 1 , u), d T (w 1 , w)) ⊆ Q uw 1 . Thus Q(d T (u 1 , u), d T (w 1 , w)) ⊆ Q(a uw 1k , b uw 1k ) ∈ Q uw 1 ( 34
)
for some k, which means a uw 1k ≤ d T (u 1 , u) and b uw 1k ≤ d T (w 1 , w). Now suppose both S 2 ∩ T u and S 2 ∩ T w are nonempty. Proceeding in the same fashion, we select vertices u 2 ∈ S 2 ∩ T u and w 2 ∈ S 2 ∩ T w such that

Q(d T (u 2 , u), d T (w 2 , w)) ⊆ Q(a uw 2 j , b uw 2 j ) ∈ Q uw 2 (35)
for some j, so that a uw 2 j ≤ d T (u 2 , u) and b uw 2 j ≤ d T (w 2 , w). Then

e(T ) ≥ d T (u 1 , w 2 ) = d T (u 1 , u) + ℓ(u, w) + d T (w, w 2 ) ≥ a uw 1k + ℓ(u, w) + b uw 2 j . (36)
Similarly,

e(T ) ≥ d T (u 2 , w 1 ) = d T (u 2 , u) + ℓ(u, w) + d T (w, w 1 ) ≥ a uw 2 j + ℓ(u, w) + b uw 1k . ( 37
)
This establishes the lemma in this case.

For the case when S 2 ∩ T u = / 0, select u 1 , w 1 , and w 2 and before, let j = 1, and note in this case that

d G (w, w 2 ) = max v∈S 2 d G (w, v) ≥ b uw 21 . As before, e(T ) ≥ d T (u 1 , w 2 ) = d T (u 1 , u) + ℓ(u, w) + d T (w, w 2 ) ≥ a uw 1k + ℓ(u, w) + b uw 21 . (38)
Now the hypothesis that d T (w, w 1 )

≤ 1 2 d T (u 1 , w 1 ) implies d T (u 1 , w) ≥ d T (w, w 1 ). Thus e(T ) ≥ d T (u 1 , w 2 ) = d T (u 1 , w) + d T (w, w 2 ) ≥ d T (w, w 1 ) + d T (w, w 2 ) ≥ b uw 1k + d G (w, w 2 ) (39) = b uw 1k + ℓ(u, w) + a uw 20 = b uw 1k + ℓ(u, w) + a uw 21 .
The case when S 2 ∩ T w = / 0 is similar, with j = N uw 2 , in light of the symmetrical relationship between a and b.

✷

Theorem 3 e(G) = min (u, w), k, j max(a uw 1k + ℓ(u, w) + b uw 2 j , a uw 2 j + ℓ(u, w) + b uw 1k ) (40)
Proof The proof is immediate from Lemmas 7 and 8. ✷

The algorithm

Moving from Theorem 3 to an explicit algorithm is mostly straightforward. One fine point is that instead of evaluating a uw 1k + b uw 2 j and a uw 2 j + b uw 1k for all combinations of k and j, a single pass can be made from k = 1, j = 1 to k = N uw 1 , j = N uw 2 since the coordinates are ordered. Calculating the values a uw ik and b uw ik is most easily understood in terms of finding the lower-left-hand corners in the boundary between L uw i and Q uw i , which is formed from horizontal and vertical line segments. The method used in Figure 5 is but one of several possible ways to solve this geometric problem.

The algorithm is shown in Figures 4 and5. First, the weighted distances between all pairs of points are calculated. Second, for each vertex v, a list H 0 [v] is created of all vertices in order of increasing distance from v. Third, by selecting just members of

S i from H 0 [v], lists H 1 [v] and H 2 [v]
are created in which the members of S 1 and S 2 , respectively, are listed in order of increasing distance from v. Fourth, for each edge (u, w), arrays A i and B i are created such that

A i [k] = a uw ik and B i [k] = b uw ik for 1 ≤ k ≤ N uw i and i = 1, 2.
The sizes of these arrays are also recorded in N i . Finally, the arrays A i and B i are scanned in one pass to seek the minimum described in Theorem 3.

The first two steps rely only on the edge weights in the graph, and not on S 1 and S 2 . In practice, the network topology can be considered fixed, so the first two steps can be precomputed. These two offline steps can be accomplished in O(|V | 3 ) steps using Dijkstra's algorithm [START_REF] West | Introduction to Graph Theory[END_REF]. Except for steps 5.1 and 5.3, the correctness of the algorithm should be patently clear. It is a relatively straightforward problem to scan the sorted arrays A i and B i in parallel seeking the minimum value of max(A

1 [k] + B 2 [ j], A 2 [ j] + B 1 [k])
; a detailed argument is presented below that step 5.3 correctly finds this minimum. It is also a relatively straightforward problem to find the lower-left-hand corners of a nonincreasing curve in the xy-plane composed of horizontal and vertical line segments; a detailed argument is presented below that step 5.1 correctly finds these corners.

Step 5.3 makes a single pass in parallel through A i and B i , rather than checking all possible pairs. This is possible because a uw ik is an increasing function of k and b uw i j is a decreasing function of j. It is straightforward to verify the loop invariant property that at statement 5.3, e ≤ min j ′ < j or k ′ <k max(A 1

[k ′ ] + B 2 [ j ′ ], A 2 [ j ′ ] + B 1 [k ′ ].
Step 5.1 is the heart of the algorithm. It searches the boundary between L uw i and Q uw i working from upper left to lower right. Step 5.1.2 stores a large number in B i [0] just to ensure that the condition is true in the first execution of 5.1.6.2.1, thus simplifying the organization of the loop. Final values are assigned to A i [0], A i [1], and B i [0], in steps 5.1.1, 5.1.4, and 5.1.7, respectively. Loop 5.1.6 works through the members of S i in order of decreasing distance from w. Within the loop, A i [k] and B i [k] (except for B i [0]) have been given their final values and A i [k + 1] and B i [k + 1] are being updated. Since the vertices are visited in order of decreasing distance from w, and since they are all within L uw i , vertex v satisfies one of three conditions: (i) v lies on the horizontal line through (a uw ik , b uw ik ); (ii) otherwise, v lies on or to the left of the vertical line through (a uw i,k+1 , b uw i,k+1 ); (iii) otherwise, v lies on the horizontal line segment to the right of (a uw i,k+1 , b uw i,k+1 ). In the first case, step 5.1.6.2.2 responds to the fact that a uw i,k+1 ≥ d G (v, u). In the third case, steps 5.1.6.2.1 and 5.1.6.2.2 finalize the value of b uw i,k+1 , initialize a uw i,k+2 , and move k forward. It is easy to see that for every lower-left corner point (a uw ik , b uw ik ), condition (iii) will occur exactly once and (i) and (iii) together will occur once for each vertex on the line segment b uw ik = y, a uw ik ≤ x. Thus the coordinates of all lower left corners will be left in A i and B i by the time the loop terminates, with the possible exception of k = 1 and k = N uw i which depend on the entry and exit conditions of the loop. It is easy to see that k = 1 is handled properly and that k = N uw i is handled properly when there is a vertex v with d G (v, w) = b uw i0 .

Step 5.1.8 tests for this last situation, adding the final lower-left corner when necessary.

Fig. 2 :D uw 1 = 2 =

 212 Fig. 2: An example problem graph. The algorithm is mostly easily understand with reference to some geometric relationships in the xyplane. If (a, b) is a point in the xy-plane, denote by Q(a, b) the open quarter plane to the upper-right of (a, b); i.e., Q(a, b) = {(x, y) | x > a and y > b}. Given a fixed reference point (a 0 , b 0 ), denote by L (a 0 ,b 0 ) (a, b) the closed rectangle to the lower left of (a, b); i.e., L (a 0 ,b 0 ) (a, b) = {(x, y) | a 0 ≤ x ≤ a and b 0 ≤ y ≤ b}. (10) If a 0 > a or b 0 > b, L (a 0 ,b 0 ) (a, b) is empty.

Fig. 3 :

 3 Fig. 3: The geometric interpretation for edge (u, w) and S 1 .

Proof

  Consider the line in the xy-plane through (a uw 1k , b uw 1k ) with slope 1. It intersects the boundary of Q uw 2 in a point (a, b) = (a uw 1k + λ, b uw 1k + λ). Since the line has slope 1, b

  The running time of step 3 is O(|V | 2 ). The running time of steps 5.1 and 5.3 are each O(|S 1 + S 2 |), so the time for step 5 is

Fig. 4 :

 4 Fig. 4: The algorithm. O(|E| |S 1 + S 2 |). Thus the offline portion of the algorithm has time complexity O(|V | 3 ) and the online portion O(|E| |S 1 + S 2 |) ≤ O(|V | |E|) ≤ O(|V | 3 ).Except for steps 5.1 and 5.3, the correctness of the algorithm should be patently clear. It is a relatively straightforward problem to scan the sorted arrays A i and B i in parallel seeking the minimum value of max(A 1 [k] + B 2 [ j], A 2 [ j] + B 1 [k]); a detailed argument is presented below that step 5.3 correctly finds this minimum. It is also a relatively straightforward problem to find the lower-left-hand corners of a nonincreasing curve in the xy-plane composed of horizontal and vertical line segments; a detailed argument is presented below that step 5.1 correctly finds these corners.Step 5.3 makes a single pass in parallel through A i and B i , rather than checking all possible pairs. This is possible because a uw ik is an increasing function of k and b uw i j is a decreasing function of j. It is straightforward to verify the loop invariant property that at statement 5.3, e ≤ min j ′ < j or k′ <k max(A 1 [k ′ ] + B 2 [ j ′ ], A 2 [ j ′ ] + B 1 [k ′ ].Step 5.1 is the heart of the algorithm. It searches the boundary between L uw i and Q uw i working from upper left to lower right. Step 5.1.2 stores a large number in B i[0] just to ensure that the condition is true

Fig. 5 :

 5 Fig. 5: Calculating A i and B i .

  1 2 d T (u ′ , w ′ ) and d T (w, w ′ ) ≤ Proof Without loss of generality, assume i = 1. If the edge (u, w) is deleted from T , two trees are produced; denote by T u the one containing u and by T w the one containing w. Because (u, w) lies in an S 1 -critical path, both S 1 T u and S 1 T w are nonempty. Let u 1 ∈ S 1 ∩ T u be chosen to maximize the value d G (u 1 , u). Let w 1 ∈ S 1 ∩ T w be chosen to maximize the value d G (w 1 , w). Then for every v ∈ S 1 , either

	1 2 d T (u ′ , w ′ ). (There are either one or two such edges.) Then for some Q(a uw 1k , b uw 1k ) ∈ Q uw 1 and Q(a uw 2 j , b uw 2 j ) ∈ Q uw 2 , e(T ) ≥ max(a uw 1k + ℓ(u, w) + b uw 2 j , a uw 2 j + ℓ(u, w) + b uw 1k ) (31)

Conclusions

We presented an algorithm for the construction of a minimum eccentricity multicast tree on general networks. Further work would naturally include a distributed version of the algorithm. Furthermore, it would be interesting to incorporate other measures of goodness such as the minimization of the total cost of the multicast tree. This would turn our problem into an NP-complete problem that requires special treatment though heuristic/approximation algorithms.


C D Randazzo

H P L Luna

P Mahey
email: mahey@isima.fr

Benders Decomposition for Local Access Network Design with Two Technologies

Keywords:

We have worked with the local access network design problem with two cable technologies. This is an optimization problem in graphs that consists of linking an origin node to a set of terminal nodes which have a flow demand. There are also a set of Steiner or transshipment nodes which do not have demand. Each arc of the graph has two associated costs: a variable cost depending on the flow through the arc and a fixed cost associated with the installation of the arc. Moreover, in each arc we can install one of two available technologies: optical fiber or copper (we can also use radio links with any other cable technology). Each one of these technologies has different variable and fixed costs. To be more precise, the fixed cost of the optical fiber is greater than that of the copper, but its variable cost is much smaller.

The problem was modeled using a multicommodity flow formulation in which we added some structural constraints. This model was used to apply the Benders decomposition method. The structural constraints have the objective of trying to guarantee that the master problem of the Benders decomposition will yield a tree. The Benders subproblems are trivial network flow problems. The dual variables have commodity meaningfull values and are evaluated in a systematic form. The algorithm was implemented in C++ with CPLEX 3.0 callable library. We have tested the algorithm with some test instances obtained by a generator of problems that we developed.

Introduction

This article addresses an extension of the local access network design problem (LAND). In the LAND problem we have to connect an origin node to a set of demand nodes minimizing the total cost. That cost is made of two parts: a variable cost which depends on the flow passing through the arc and a fixed cost to install the arc. There are also transshipment or Steiner nodes that do not have any demand and can be used or not in the optimal topology. In the problem that we work with in this paper, we can install one of two available technologies, for instance, optical fiber or copper cables, in each arc of the network. Note that it is also possible to think about radio links as an alternative to one of these cable technologies. We call this problem the local access network design problem with two technologies (LAND-2T). We will follow the notation given in [START_REF] Balakrishnan | Modeling and heuristic worst-case performance analysis of two-level network design problem[END_REF] and will denote the two kinds of links by "primary links" (optical fiber) and "secondary links" (copper). The copper cable has a fixed cost smaller than that of the optical fiber, but its variable cost is greater than the variable cost of the optical fiber. We also work with primary connectivity constraints that require that primary links be connected to the origin node by a path consisting of primary links only. The reason for using such constraints is that a message which flows from one technology link to another technology link has to undergo some kind of data transformation which implies that a switching device has to be installed at every node where a change of technology takes place. In our problem, the primary connectivity constraints ensure that the number of such devices will be small and the cost of installing these devices is not considered. Another reason for requiring the primary connectivity constraints is that they imply that more paths can benefit from the higher quality of the primary links.

There are many possible variations of the LAND-2T problem that result in new problems. Balakrishnan et al. [START_REF] Balakrishnan | A dual-based algorithm for multi-level network design[END_REF] have worked with a problem similar to the LAND-2T where a minimum cost spanning tree that contains an embedded primary subtree connecting all the primary nodes (and optionally including secondary nodes) has to be found. As in the LAND-2T, one can install one of two available cable technologies for each arc. Note that they divide the set of nodes into primary and secondary nodes. The primary nodes have to be connected to the origin node by primary arcs. The secondary nodes can be linked to the origin node by primary or secondary arcs. They have proposed a dual-ascent algorithm to find an approximate solution.

Gouveia and Janssen [START_REF] Gouveia | Designing reliable tree networks with two cable technologies[END_REF] have worked with a similar problem that is an extension of the minimal spanning tree problem, but with two cable technologies too. The model that they explore has generalized hop constraints and primary connectivity constraints. Hop constraints limit the number of links (hops) between the root node and any terminal and measure in a certain way the reliability of the tree network. The primary connectivity constraints are the same that we described above. The problem is shown to be NP-hard and procedures to obtain lower and upper bounds are presented. They formulate the problem as a directed multicommodity flow model. To derive lower bounds they use Lagrangean relaxation with subgradient optimization. A Lagrangean heuristic is developed to construct feasible solutions. Moreover, they discuss several different ways of modeling the primary connectivity constraints. One outcome of their discussion is that an extended and compact representation of the convex hull of directed rooted subtrees when the underlying graph is series-parallel can be derived.

De Jongh et al. [START_REF] De Jongh | Finding disjoint routes in telecommunications networks with two technologies[END_REF] have also worked with a closely related problem in which a pair of nodes has to be linked by two node disjoint paths with minimum total cost and two cable technologies. This problem is a little different from the LAND-2T since for each arc of the network there is only one available technology, that is, each arc has a specified technology and there are arcs of type 1 and arcs of type 2. In the LAND-2T problem, for each arc we have two available technologies. They also consider a transition cost that is associated with each node. This cost is incurred only when a flow enters and leaves the corresponding node on arcs of different types. Two heuristics were proposed in [START_REF] De Jongh | Finding disjoint routes in telecommunications networks with two technologies[END_REF] and a lower bounding procedure based on Lagrangean relaxation is provided. These procedures are used in a branchand-bound strategy to solve the problem.

In a previous paper, we worked with the local access network design problem [START_REF] Luna | Experiments on optimal methods for local access network design[END_REF]. In this article, we studied two formulations of the problem: single commodity flow formulation; multicommodity flow formulation. The problem was solved exactly by CPLEX (with the two formulations), by a branch-andbound algorithm, by a branch-and-cut algorithm and by a Benders decomposition. The success obtained by Benders decomposition to solve this problem has induced us to extend the algorithm developed to the local access network design problem to solve the LAND-2T. In Section 2 the mathematical programming formulation of the problem is presented. Section 3 presents the Benders decomposition applied to solve the problem. The implemented algorithm is showed in Section 4. Section 5 presents and discusses the computational results obtained. Section 6 closes this article with conclusions and final comments.

Formulation of the Problem

Consider a directed connected graph G(V, E), where V denotes the set of nodes and E is a collection of directed arcs. Each arc of the graph represents a possible pair of nodes between which a directed transmission link can be placed. This transmission link can be a primary or a secondary link. Suppose we have an origin node o that must be linked to a number of |K| demand nodes, each of them with a commodity flow requirement of d k , where k ∈ K and K ⊆ V .

With appropriate structural and operational costs, the problem is to find a minimal cost arborescence that links the origin node to all the terminal nodes and that has a connected set of primary links beginning from the origin node. Remark that all flows are originated at the origin node.

We define the variables:

x i j1 = 1 if a direct primary transmission link is placed in arc (i, j) 0 otherwise;

x i j2 = 1 if a direct secondary transmission link is placed in arc (i, j) 0 otherwise; f i jk1 : flow passing through the primary arc (i, j) and destinated to the demand node k. f i jk2 : flow passing through the secondary arc (i, j) and destinated to the demand node k.

And we also define the cost parameters:

b i j1 : fixed (structural) cost to install a direct primary transmission link in (i, j); b i j2 : fixed (structural) cost to install a direct secondary transmission link in (i, j); c i jk1 : variable (operational) cost to transmit one unit of commodity k through the primary arc (i, j); c i jk2 : variable (operational) cost to transmit one unit of commodity k through the secondary arc (i, j);

The mathematical model, M, for the LAND-2T problem is:

min ∑ (i, j)∈E (b i j1 x i j1 + b i j2 x i j2 + ∑ k∈K (c i jk1 f i jk1 + c i jk2 f i jk2 )) (1)
subject to:

-∑ (o, j)∈E ( f o jk1 + f o jk2 ) = -d k , for node o and ∀k ∈ K (2) ∑ (i,k)∈E ( f ikk1 + f ikk2 ) = d k , ∀k ∈ K (3) ∑ (i, j)∈E ( f i jk1 + f i jk2 ) -∑ ( j,l)∈E ( f jlk1 + f jlk2 ) = 0∀ j ∈ V -{o} and j = k and ∀k ∈ K (4) f i jk1 ≤ d k x i j1 , ∀(i, j) ∈ E and ∀k ∈ K (5) f i jk2 ≤ d k x i j2 , ∀(i, j) ∈ E and ∀k ∈ K (6) f i jk1 ≥ 0 , ∀(i, j) ∈ E and ∀k ∈ K (7) f i jk2 ≥ 0 , ∀(i, j) ∈ E and ∀k ∈ K (8) ∑ (i,k)∈E (x ik1 + x ik2 ) = 1 , ∀k ∈ K (9) ∑ (l, j)∈E (x l j1 + x l j2 ) -∑ (i,l)∈E (x il1 + x il2 ) ≥ 0 , ∀l ∈ V -K (10) ∑ (i,l)∈E (x il1 + x il2 ) ≥ ∑ (l, j)∈E (x l j1 + x l j2 ) ∑ (l, j)∈E 1 , ∀l ∈ V -K -{o} (11)
x i j1 + x i j2 + x ji1 + x ji2 ≤ 1 , ∀(i, j) ∈ E (12) ∑ (l,i)∈E x li1 ≥ x i j1 , (i, j) ∈ E , ∀i ∈ V -{o} (13) x i j1 , x i j2 ∈ {0, 1} , ∀(i, j) ∈ E (14)
The objective function minimizes the total cost associated with the fixed and variable costs. Constraints (2) ensure that the flow of commodity k that leaves the origin node is equal to the demand of the node k. Constraints (3) guarantee that the flow of commodity k that arrives at node k is equal to its demand. Constraints (4) are flow conservation constraints. The fact that a flow can pass through an arc only if this arc is selected to the design is expressed by constraints (5) (for primary arcs) and (6) (for secondary arcs). Constraints (7) and (8) ensure that the flow variables are greater than zero. Constraints from (9) to (13) are redundant, but they are important to try to guarantee that the solution of the master problem resulting of Benders decomposition is an arborescence (Benders decomposition method will be described in the next section). We call these constraints structural constraints. Constraints (9) ensure that at each demand node enters only one arc. Constraints (10) guarantee that at each Steiner node the number of nodes that leave the node is greater than or equal to the number of arcs that enter the node. Constraints (11) express the fact that if at least one arc leaves the node l, then at least one arc enters the node l. Between any nodes i and j the number of selected arcs, in any direction, has to be less than or equal to 1. Constraints (12) express this fact. Constraints (13) are the primary connectivity constraints and guarantee that the set of primary arcs constitutes a connected set from the origin. Finally, constraints (14) define the binary variables x i j .

Benders Decomposition of the Problem

Benders partitioning method was published in 1962 [START_REF] Benders | Partitioning procedures for solving mixed integer variables programming problems[END_REF] and was initially developed to solve mixed integer programming problems. The computational success of the method to solve large scale multicommodity distribution system design models has been confirmed since the pioneering paper of Geoffrion and Graves [START_REF] Geoffrion | Multicomodity distribution system design by Benders decomposition[END_REF]. Florian et al. [START_REF] Florian | The engine scheduling problem in a railway network[END_REF] have used Benders decomposition to schedule the movement of railways engines and Richardson [START_REF] Richardson | An optimization approach to routing aircraft[END_REF] has applied the algorithm to airline routing. Fisher and Jaikumar [START_REF] Fisher | A decomposition algorithm for large scale vehicle routing[END_REF] have discussed the advantages of using the algorithm for vehicle routing problems. Magnanti and Wong [START_REF] Magnanti | Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria[END_REF] have proposed methodology for improving the performance of Benders decomposition when applied to mixed integer programs. They have introduced a technique for accelerating the convergence of the algorithm and theory for distinguishing "good" model formulations of a problem that has distinct, but equivalent mixed integer programming representations. In [START_REF] Magnanti | Tailoring Benders decomposition for uncapacitated network design[END_REF], Magnanti et al. have applied Benders decomposition to solve the uncapacitated network design problem (with undirected edges) and have adapted this technique to be as efficient as possible. In [AB97], Benders decomposition is applied for solving network design problems with underlying tree structure. In [LRM98] Benders decomposition method was used to solve the local access network design problem and performed better than branch-and-cut and branch-and-bound algorithms.

Master Problem

The mathematical model of the master problem is constituted by the following objective function:

min ∑ (i, j)∈E (b i j1 x i j1 + b i j2 x i j2 ) + t (15)
subject to the constraints (9), ( 10), ( 11), ( 12), ( 13), ( 14) and by the Benders cut constraint

t ≥ ∑ k∈K d k (p h kk -∑ (i, j)∈E (α h i jk1 x i j1 + α h i jk2 x i j2 )), h = 1, 2, ..., H (16)
The parameter h is a cycle counter and indicates the number of Benders cuts that must be taken into account. For given h and k, the corresponding value in the right-hand-side of constraints ( 16) provides a lower bound on the cost of the flow that leaves the origin node to the demand node k.

Consequently, there are three series of dual variables that can be interpreted as prices informations:

• p h lk : price of opening the communication k (k ∈ K) at node l (l ∈ V ) in cycle h (h = 1...H), • α h i jk1 : maximal reduction in the operational cost of commodity k if the primary link at arc (i, j) is selected to the design in cycle h,

• α h i jk2 : maximal reduction in the operational cost of commodity k if the secondary link at arc (i, j) is selected to the design in cycle h.

The real variable t that appears in objective function ( 15) is a lower bound on the total operational cost.

Subproblems

For a fixed arborescence A h , associated with the vectors x h 1 and x h 2 , we have to solve separately a series of trivial network flow problems. Let C h ok1 be the set of arcs of type 1 in the path from the source node to the demand node k and C h ok2 be the set of arcs of type 2 in the path from the source node to the demand node k that have been defined by the master problem of cycle h. The primal-dual pair to be solved for commodity k is:

min ∑ (i, j)∈A (c i jk1 f h i jk1 + c i jk2 f h i jk2 ) (17)
subject to:

-∑ (o, j)∈E ( f h o jk1 + f h o jk2 ) = -d k for the root o (18) ∑ (i,k)∈E ( f h ikk1 + f h ikk2 ) = d k for node k (19) ∑ (i, j)∈E ( f h i jk1 + f h i jk2 ) -∑ ( j,l)∈E ( f h jlk1 + f h jlk2 ) = 0 ∀ j ∈ V -{o} and j = k (20) -f h i jk1 ≥ -d k ∀(i, j) ∈ A h (21) -f h i jk2 ≥ -d k ∀(i, j) ∈ A h (22) f h i jk1 ≥ 0 ∀(i, j) ∈ A h ( 23
)
f h i jk2 ≥ 0 ∀(i, j) ∈ A h (24)
The trivial and unique solution of the problem is:

f h i jk1 = d k if (i, j) ∈ C h ok1 ⊆ A h 0 otherwise f h i jk2 = d k if (i, j) ∈ C h ok2 ⊆ A h 0 otherwise
The dual subproblem for commodity k is:

max p h ,α h ≥0 d k (-∑ (i, j)∈A h (α h i jk1 + α h i jk2 ) + p h kk -p h ok ) (25)
subject to:

p h jk -p h ik -α h i jk1 ≤ c i jk1 ∀(i, j) ∈ E (26) p h jk -p h ik -α h i jk2 ≤ c i jk2 ∀(i, j) ∈ E (27) α h i jk1 , α h i jk2 ≥ 0 ∀(i, j) ∈ E (28) p h ik unrestricted ∀i ∈ V (29)
From the complementary slackness condition we have:

p h jk -p h ik -α h i jk1 = c i jk1 ∀(i, j) ∈ C h ok1 ⊂ A h ( f i jk1 = d k ) p h jk -p h ik -α h i jk2 = c i jk2 ∀(i, j) ∈ C h ok2 ⊂ A h ( f i jk2 = d k )
in such a way that we can construct, associated with the primal solution x h , the following dual feasible solution:

p h ok = 0 ∀k ∈ K for the origin node o (30) p h jk = p h ik + c i jk1 ∀(i, j) ∈ C h ok1 ⊂ A h (31) p h jk = p h ik + c i jk2 ∀(i, j) ∈ C h ok2 ⊂ A h (32) p h ik = p 0 ik ∀i ∈ V -V h (33) α h i jk1 = 0 ∀(i, j) ∈ C h ok1 ⊂ A h (34) α h i jk1 = p h jk -p h ik -c i jk1 ∀(i, j) ∈ E -C h ok1 such that p h jk -p h ik > c i jk1 (35) α h i jk1 = 0 ∀(i, j) ∈ E -C h ok1 such that p h jk -p h ik ≤ c i jk1 (36) α h i jk2 = 0 ∀(i, j) ∈ C h ok2 ⊂ A h (37) α h i jk2 = p h jk -p h ik -c i jk2 ∀(i, j) ∈ E -C h ok2 such that p h jk -p h ik > c i jk2 (38) α h i jk2 = 0 ∀(i, j) ∈ E -C h ok2 such that p h jk -p h ik ≤ c i jk2 (39)
The systematic evaluation of the dual variables with commodity meaningful values is a key factor for an efficient implementation. The dual variable α h i jk1 evaluates for commodity k the maximal reduction in the operational cost that could be gained with the introduction of a primary link at the arc (i, j) in the solution. It can also be understood as a tax to be paid with the use of the primary arc (i, j) in order to maintain the distribution agents with no positive profit. Remark that the dual solution set represents spatial prices for which there is no positive profit for any distribution agent that pays the cost c i jk1 to flow commodity k across the primary arc (i, j). The same interpretation is valid for the dual variables α h i jk2 .

Algorithm

In this section we present the implemented algorithm. Our algorithm is not simply a Benders decomposition algorithm. We work with a special feasible solution of the problem that minimizes the total variable cost. This solution is obtained applying the Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connection with graphs[END_REF] to find the shortest path from the origin to all nodes, but only the variable cost to flow from origin to each demand node is computed. The main steps of the algorithm are the following:

1. Use Dijkstra's algorithm to find the shortest path from the origin o to every node of the network. Let E 0 be the arcs of the arborescence that contains the shortest paths to all the nodes and let T (V 0 , A 0 ) be the correspondent arborescence that links the origin o to all demand nodes k ∈ K (x

0 i j1 = 1 ∀(i, j) ∈ A 0 , x 0 i j1 = 0 ∀(i, j) ∈ E -A 0 and x 0 i j2 = 0 ∀(i, j) ∈ E). Make p 0 ok = 0 ∀k ∈ K, for the origin node o p 0 jk = p 0 ik + c i jk1 ∀(i, j) ∈ E 0 , ∀k ∈ K across E 0 α 0 i jk1 = 0 ∀(i, j) ∈ E, ∀k ∈ K α 0 i jk2 = 0 ∀(i, j) ∈ E, ∀k ∈ K
Compute the cost associated with T (V 0 , A 0 ) (the sum of the fixed cost of the arcs in A 0 plus the sum of the variable costs of sending the flow requirement of each demand node k from the origin to the demand node). This value gives an initial upper bound, UB = ∑ (i, j)∈A 0 (b i j1 x 0 i j1 + b i j2 x i j2 ) + ∑ k∈k d k p 0 kk , and (x 0 1 , x 0 2 , f 0 ) is an incumbent solution. Also, the shortest paths solution provides the minimal total variable cost among all possible arborescences, and thus we can use it to initialize the lower bound, LB = ∑ k∈k d k p 0 kk . This is also a lower bound on the variable t of the master problem.

2. Initialize the cycle counter with zero, i. e., h = 0.

3. Solve the master problem. It provides a lower bound for the problem. If the lower bound is greater than (or equal to) the upper bound, then stop.

Increment the cycle counter, h.

5. Solve the subproblem. To solve it, verify first if the selected arcs in the master problem build an arborescence from the origin to all demand nodes.

• If they do, let T (V h , A h ) be the arborescence that links the origin o to all demand nodes k ∈ K, contained in the original graph G(V, E), let C h ok1 be the set of primary arcs in the path from the origin to the demand node k across A h , and let C h ok2 be the set of secondary arcs in the path from the origin to the demand node k.

• Else, the solution of the master problem turns the subproblem infeasible in the sense that it generates a cycle in the path from the origin to one or more demand nodes. In this case, the cycles are identified and constraints to avoid them are added to the master problem model and no new upper bound is generated. The master problem must again be solved, then go to step 3.

6. Compute the values of the dual variables shown by equations (30)-(39). A new value for the upper bound is calculated and if this value is less than the current upper bound then the current upper bound is updated. If the lower bound is greater than (or equal to) the upper bound, then stop.

7.

Add a new Benders cut to the master problem using the dual variable calculated in the previous step. Go to step 3.

Computational Results

The tests were executed on a Sun Ultra Enterprise 3000 with two 250 MHz UltraSPARC processors and 512 Mbytes of RAM memory. The operational system is Solaris 2.5.1. The Benders decomposition algorithm was implemented in C++ with CPLEX 3.0 callable library. The test problems from 1 to 5 are Euclidean graphs randomly generated using a procedure similar to that presented in [START_REF] Aneja | An integer linear programming approach to Steiner problem in graphs[END_REF]. This procedure has extensively been applied for creating testbeds of the Steiner problem and we have used this procedure to generate test instances of the local access network design problem [START_REF] Luna | Experiments on optimal methods for local access network design[END_REF]. The test problems from 6 to 10 were generated by a different procedure which has been used to generate test instances for the local access network design problem in such a way that the linear relaxation of the multicommodity flow formulation of this problem does not find an optimal integer solution. This procedure was proposed by [START_REF] Holmberg | Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound[END_REF].

Table 1 shows the results obtained by solving the test problems by CPLEX and by Benders decomposition method. The number of cycles (number of master problems solved) was small, specially for the problems from 6 to 10 for which the greatest number of cycles was 4. Benders decomposition algorithm was better than CPLEX for 6 of the 10 problems. For the problems from 6 to 10, the execution time of Benders decomposition was smaller than the execution time of CPLEX for all problems (this difference between the execution times was more significative for problems 8, 9 and 10). Although the initial gap ((upper bound -lower bound)/upper bound) obtained from the first solved master problem may be high, the performance of Benders decomposition algorithm is encouraging.

It is important to note that for all test problems in Table 1 the linear relaxation of the model M produces an optimal integer solution. We have not tested the instances which do not have this property yet. From our previous experience with one cable technology, we know that Benders decomposition may be better than other methods as branch-and-bound and branch-and-cut. So, we believe that the performance of Benders decomposition can be better than this obtained with these preliminary experiments.

Conclusions

In this article we have extended a Benders decomposition algorithm that we have previously implemented to solve the local access network design problem. This algorithm performed very well on the local access network design problem and the obtained results have lead us to extend it to solve the LAND-2T.

We have presented a multicommodity flow formulation for the LAND-2T with primary connectivity constraints. Moreover, we have added some structural constraints to the model with the objective of getting feasible solutions from the master problem. Benders decomposition was applied to this model and the values of the dual variables were derived. Some computational experiments were developed and the number of master problems solved was small, from 2 to 9. Benders decomposition has performed better than CPLEX for 6 of the 10 test problems. In some instances, Benders execution time was 10% of CPLEX execution time. We have not tested the algorithm with the instances for which the linear relaxation of model M does not find an optimal integer solution of the problem. From our previous experience, we expect that the best results of Benders decomposition algorithm will be reached for these problems.

Table 1 :

 1 Computational results for the problem LAND-2T.

	Problem				CPLEX		Benders Decomposi tion
	Number	|V |	|E|	|K| B&B Nodes Time(s) Initial Gap	Cycles T ime(s)
	1	10	40	4	0	0.75	92%	7	0.70
	2	10	50	4	0	0.27	58%	8	1.61
	3	12	50	5	0	0.10	51%	5	0.95
	4	15	50	8	0	0.11	48%	7	3.11
	5	16	60	10	0	0.31	48%	9	2.37
	6	21	112	4	0	2.40	95%	2	0.50
	7	31	220	5	0	50.07	96%	2	49.27
	8	31	240	6	0	29.79	2%	2	2.41
	9	36	322	7	0	159.08	2%	4	30.21
	10	41	417	8	0	269.69	2%	2	2.05

† Partially supported by the brazilian institutions CNPq, CAPES and FINEP/MCT (Grant 76.97.1016.00). 1365-8050 c 2001 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France