Printer Friendly

Weighted cache location problem with identical servers.

1. Introduction

Caching has become an important tool to improve the network performance efficiency, reducing delays to every client and alleviating the overload on the server [1-4]. Initially, a large amount of studies considered how to optimize cache performance [5-7], cache hierarchies [5], and cooperations among multiple web servers [8, 9]. Subsequently, how to locate caches or proxies optimally in networks to alleviate the server load became more popular [2, 10-13]. The most popular practice in the past is to place caches on the edges of networks, acting as the network browser and proxy or part of cache hierarchies [1, 3-5]. Later, Danzig et al. [2] discovered that the advantage of placing caches on the nodes of networks instead of on the edges of networks is to reduce overall network congestion greatly. In this paper, we only discuss how to place caches on the nodes of networks.

The focus of placing caches in networks is how to enhance the effect and efficiency of caching in networks as greatly as possible. This problem can be modeled as the p-cache location problem (abbreviated to p-CLP or CLP) or p-proxy problem. Both of their initial models can be reduced to the p-median problem [14, 15] essentially. Throughout this paper, we let n denote the number of network nodes, let m denote the number of network edges, let p denote the number of caches or proxies, let and h denote the height of tree. Later, Abrams et al. [7] investigated that almost all current cache products contain a transparent operation mode, called a transparent en-route cache (TERC). When using TERCs in networks with one server, all clients connect to server and caches are placed on the routes from clients to server. Heddaya and Mirdad [10] suggested making use of TERCs to balance load due to the manageability of TERC. Further, Krishnan et al. [11] proposed the cache location problem involving TERCs, studied the problem in several special networks, and presented polynomial time exact algorithms. In the rest of this paper, all of CLPs involve TERC.

The known algorithms for the p-proxy problem also apply to p-CLP. For a linear network, Li et al. studied the p-proxy problem and presented an O([pn.sup.2]) time exact algorithm [12]. Later, Woeginger used the Monge property to obtain an improved algorithm with O(pn) time complexity [16]. For a tree network, Li et al. devised an O([p.sup.2][n.sup.3])-time exact dynamic programming algorithm [13] and Chen et al. presented an improved O(nph)-time algorithm [17]. For a general tree of rings network, Chen et al. showed an O(p[n.sup.2]) time exact algorithm [18]. Moreover, a variety of objectives have been considered, such as the overall time, cost, and hop count. Du [19] and Jia et al. [20] studied the proxy problem with read-write operations. In [21], Liu and Yang considered the delay-constrained proxy problem. Given a general network, provided that all clients are intelligent and connect to the server via a shortest route on the network, we claim that p-CLP in this situation is equivalent to p-CLP on the tree and thus is solvable in polynomial time [11, 13, 17] since all the shortest routes between clients and server form a shortest-paths tree rooted at the server node.

All past works on CLP considered a single server. This paper is the first one to study CLP with multiple identical servers. In this model, every client connects to some server via a route and all caches lie on such routes. We further suppose that every client is intelligent; that is, it connects to the closest server to itself via a shortest route. This produces the closest server orienting protocol (abbreviated to CSOP). Under CSOP, all the shortest routes connecting clients and server form a forest, each component of which is rooted at a server node. Therefore, the CLP with multiple identical servers under CSOP on a general network is equivalent to that on a forest.

We abbreviate p-CLP with m identical servers to (p, m)-CLP and further (p, m)-CLP under CSOP to (p,m)-CSOP CLP. In this paper, we first propose an improved parallel exact algorithm for p-CLP on a tree, which reduces O(nph) time of algorithm in [17] to 0([ph.sup.2] + n). Based on the improved algorithm, we design a parallel exact algorithm for (p, 2)-CSOP CLP on a general network, which takes O([p.sup.2] max{[h.sup.2.sub.1], [h.sup.2.sub.2]} + (8/3)np) time and at most O((4/9)[p.sup.2][n.sup.2]) time in the worst case. Furthermore, we extend the algorithm idea to (p, m)-CSOP CLP on a general network and get a parallel exact algorithm, which takes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] time and at most O((4/9)[(n - m).sup.2]([(m + p).sup.p]/(p - 1)!)) time in the worst case.

The rest of this paper is organized as follows. In Section 2, we define notations used frequently and (p, 2)-CSOP CLP formally. In Section 3, we make some fundamental preliminaries, develop an improved algorithm for p-CLP on a tree, and then devise a parallel exact algorithm for (p, 2)-CSOP CLP based on the improved algorithm. In Section 4, we define (p, m)-CSOP CLP formally and devise an efficient parallel exact algorithm. In Section 5, we first give an example to illustrate our algorithm and then make a series of numerical experiments to compare the running time of our algorithm. In Section 6, we conclude this paper with some future research topics.

2. Problem Description

Let G = (V, E, w, c) represent a communication network or computer network, where V is the node set and E is the edge set. Every node represents a processing or switching element and every edge represents a communication link [22]. Every node z e V has a weight w(z) > 0 representing the demand amount of z, and every edge e [member of] E has a weight c(e) > 0 representing the cost per demand. For any pair of nodes x and y, we let [x, y] denote the edge of G between x and y and let [pi](x, y) denote the shortest path in G connecting x and y. Let c[x, y] denote the cost of edge [x, y], and c(x, y) denote the cost of [pi](x, y) which is equal to the sum of all the costs on edges of [pi](x, y). So,

c{x, y) = [summation over (e [member of] [pi] (x, y))] c(e). (1)

Let [s.sub.1] and [s.sub.2] be two identical servers, which are allocated to a pair of nodes of G in advance. Let [GAMMA] denote the set of p cache locations. Suppose that CSOP works and each cache is a duplicate of server. Given any set [GAMMA] [subset] V\{[s.sub.1], [s.sub.2]}, the cost of node z paying for its per demand depends on the locations of [GAMMA] [union] {[s.sub.1], [s.sub.2]} and is denoted by c(z, [GAMMA] [union] {[s.sub.1], [s.sub.2]}). Thus, the cost of z paying for its overall demand is equal to w(z)c(z, [GAMMA] [union] {[s.sub.1], [s.sub.2]}). Let f([GAMMA]) denote the total cost of all the nodes paying for their overall demand, that is,

f([GAMMA]) = [summation over (z [member of] V)] w(Z)c(z, [GAMMA] [union] {[s.sub.1], [s.sub.2]}). (2)

The p-cache location problem with two identical servers under CSOP (i.e., (p, 2)-CSOP CLP) aims to find p cache locations in G to minimize the total cost of all the nodes paying for their overall demand. In other words, the aim of (p, 2)-CSOP CLP can be reduced to find an optimal set [[GAMMA].sup.*] from V\{[s.sub.1], [s.sub.2]} to minimize the value of f([GAMMA]), that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

3. A Parallel Exact Algorithm for (p,2)-CSOP CLP

In the scenario of (p, 2)-CSOP CLP, every client knows the location of the closest server to itself and connects to it via a shortest route. If its service request encounters the closest cache on the route, it will get information therein. Otherwise, it get information from the server. Therefore, (p, 2)-CSOP CLP can be viewed as the combination of two CLPs when [s.sub.1] and [s.sub.2] are predesignated to two locations of network. One is CLP with [s.sub.1] as the server and the other is CLP with [s.sub.2] as the server.

3.1. Preliminaries. Once [s.sub.1] and [s.sub.2] are fixed at two predesignated locations of G, it is certain that some nodes of G are closer to [s.sub.1] and the other nodes are closer to [s.sub.2]. Let V([s.sub.1]) be the set of nodes that are closer to [s.sub.1] and V([s.sub.2]) be the set of nodes that are closer to [s.sub.2]. Thus, Lemma 1 follows immediately. Let T([s.sub.1]) (resp. T([s.sub.2])) denote the single-source shortest paths tree in G with s1 (resp. [s.sub.2]) as the origin spanning V([s.sub.1]) (resp. V([s.sub.2])). We can use Dijkstra's algorithm [23] to compute T([s.sub.1]) and T([s.sub.2]). We can transform T([s.sub.1]) (resp. T([s.sub.2])) into a rooted tree with [s.sub.1](resp. [s.sub.2]) as the root without loss of generality. Furthermore, let [T.sub.x]([s.sub.1]) denote the subtree of T([s.sub.1]) rooted at x for any x [member of] V([s.sub.1]) and let [T.sub.y]([s.sub.2]) denote the subtree of T([s.sub.2]) rooted at y for any y [member of] V([s.sub.2]).

Lemma 1. V = V([s.sub.1]) [union] V([s.sub.2]).

Specifically, we let [PI] [[s.sub.1], [s.sub.2]] denote the unique path on tree between [s.sub.1] and [s.sub.2] when G is a tree graph. Let N([s.sub.1]) (resp. N([s.sub.2])) be the set of nodes on n[[s.sub.1], [s.sub.2]] which are closer to [s.sub.1] (resp. [s.sub.2]) and let [V.sub.x]([s.sub.1], [s.sub.2]) be the subset of nodes which reach [s.sub.1] and [s.sub.2] via x for any node x on [PI][[s.sub.1], [s.sub.2]]. We investigate that every node in [V.sub.x]([s.sub.1], [s.sub.2]), x [member of] N([s.sub.1]) belongs to V([s.sub.1]) and every node in [V.sub.y]([s.sub.1], [s.sub.2]), y [member of] N([s.sub.2]) belongs to V([s.sub.2]), and vice versa. So, Lemma 2 follows. By Lemmas 1 and 2, we can compute T([s.sub.1]) and T([s.sub.2]) by applying the depth-first search (DFS) procedure to the tree, which only takes a linear time.

Lemma 2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Lemma 1, we are sure that one cache is placed either in V([s.sub.1]) or V([s.sub.2]). The set of cache locations in V([s.sub.1]) and V([s.sub.2]) is denoted by [GAMMA]([s.sub.1]) and [GAMMA]([s.sub.2]), respectively; thus, [GAMMA] = [GAMMA]([s.sub.1]) [union] [GAMMA]([s.sub.2]), [GAMMA]([s.sub.1]) = [GAMMA] [intersection] V([s.sub.1]) and [GAMMA]([s.sub.2]) = [GAMMA] [intersection] V([s.sub.2]). Under CSOP, every z [member of] V([s.sub.1]) connects to [s.sub.1] and thus the cost of paying for its overall demand is equal to w(z) - c(z, [GAMMA]([s.sub.1]) [union] {[s.sub.1]}). Similarly, the cost of z [member of] V([s.sub.2]) is equal to w(z) x c(z, [GAMMA]([s.sub.2]) [union] {[s.sub.2]}). We can further rewrite (2) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Let [p.sub.1] be the number of caches in [GAMMA]([s.sub.1]) and let [p.sub.2] be the number of caches in [GAMMA]([s.sub.2]). Obviously, [p.sub.1] + [p.sub.2] = p. A combination of [GAMMA]([s.sub.1]) having [p.sub.1] caches and [GAMMA]([s.sub.2]) having [p.sub.2] caches is called a cache allocation scheme (abbreviated to CAS), denoted as ([p.sub.1], [p.sub.2])-CAS where [p.sub.1] and [p.sub.2] cannot be exchanged. Clearly, (p, 2)-CSOP CLP contains p + 1 CASs in total. For any ([p.sub.1], [p.sub.2])-CAS, (p, 2)-CSOP CLP is composed of two subproblems, that is, [p.sub.1]-CLP in T(s1) and [p.sub.2]-CLP in T([s.sub.2]). Let C(G, p) denote the minimum cost of (p, 2)-CSOP CLP in G, and let C(T([s.sub.1]), [p.sub.1]) denote the minimum cost of [p.sub.1]-CLP in T([s.sub.1]) and let C(T([s.sub.2]), [p.sub.2]) denote the minimum cost of [p.sub.2]-CLP in T([s.sub.2]). The cost of (p, 2)-CSOP CLP in G for any given ([p.sub.1], [p.sub.2])-CAS is equal to the sum of C(T([s.sub.1]), [p.sub.1]) and C(T([s.sub.2]), [p.sub.2]), and further C(G, p) results from the optimal ([p.sub.1], [p.sub.2])-CASs; that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

3.2. Preprocessing. In this subsection, we give a new method of transforming an arbitrary rooted tree into a binary tree. Let T be a rooted tree. For any nonleaf node x of T, the subgraph of T is composed of the edges between x and all its children are called a star of T with center x, denoted by star(x). Let d(x) denote the number of children of x. We process x in the following way:

(i) if d(x) = 1, then we add a new child y' to x and set both c[x, y'] and w(y') to zero;

(ii) if d(x) = 2, then we need no work;

(iii) if d(x) = k, k [greater than or equal to] 3 (let all children of x be [x.sub.1], [x.sub.2], ..., [x.sub.k]), then we delete the edges (x, [x.sub.1]), (x, [x.sub.2]), ..., (x, [x.sub.k]), add two new nodes y and y" to x, and set w(y'), c(x, y') and w(y"), c(x, y") to zero. For each t = 1, 2, ..., [k/2], we add new edge (y', [x.sub.t]) and set c(y', [x.sub.t]) to c(x, [x.sub.t]). For each t = [k/2] + 1, ..., k, we add new edge (y", [x.sub.t]) and set c(y", [x.sub.t]) to c(x, [x.sub.t]).

We use the above way recursively to process every node of T = (V, E, w, c) top-down to obtain a binary tree b(T) = ([V.sub.b], [E.sub.b], [w.sub.b], [c.sub.b]). This idea can be described as algorithm BINY. Our way improves that one proposed by Chen et al. [18]. Moreover, we will analyze the performance of BINY in the following while they provided no analysis of their algorithm [18].

Theorem 3. For each x of T with d(x) = k [greater than or equal to] 3, the subtree of b(T) derived from transforming star(x) by BINY has a height of 0(log k) and has 5k/3 - 2 dummy nodes added in the worst case.

Proof. The essence of BINY processing star(x) is to bisect all the children of x recursively. At the final step, two dummy nodes are added if four nodes are bisected into two groups of two nodes and three dummy nodes are added if three nodes are bisected into one group of two nodes and one group of one node. So, BINY adds the most dummy nodes in the worst case of k = 3 x [2.sup.t]. In this case, the subtree of k(T) derived from transforming star(x) by BINY has a height of t + 2 and the number of dummy nodes added is 2(1 - [2.sup.t])/(1 - 2) + 3 x [2.sup.t] = 5 x [2.sup.t] - 2. In fact, we investigate that the subtree of k(T) derived from a star with k nodes satisfying that [2.sup.t+1] + 1 < k [less than or equal to] [2.sup.t+2] has a height of t + 2. So, log k [less than or equal to] t + 2 < log k + 1. Therefore, the subtree of k(T) derived from star(x) has a height of O(log k). The number of all the dummy nodes added by BINY in the worst case is 5 x [2.sup.t] - 2 = 5 x 2[log.sup.(k/3)] - 2 = 5k/3 - 2.

Theorem 4. BINY can transform T with n nodes into k(T) with a height of at most 2(n - 1)/3, which takes O(n) time and adds at most (5/3)n - 11/3 dummy nodes.

Proof. Suppose that T has K stars and every star([x.sub.i]), 1 [less than or equal to] i [less than or equal to] K, has children. Obviously, [[summation].sup.K.sub.i=1] = [absolute value of E] = n - 1. By Theorem 3, BINY adds 5[k.sub.i]/3 - 2 dummy nodes for every stflr(x;) in the worst case of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the number of dummy nodes added by BINY is [[summation].sup.K.sub.i=1] (5[k.sub.i]/3 - 2) = (5/3) [[summation].sup.K.sub.i=1] [k.sub.i] - 2K [less than or equal to] (5/3)(n - 1) - 2 = (5/3)n - 11/3.

Next, we discuss the height of k(T). We construct a worst-case tree [T.sup.[DELTA]] consisting of K three-children stars lined one by one. In other words, for every star of T other than the bottom one, two children of the star are leaves of T and the other one is the center of the next star. Clearly, [T.sup.[DELTA]] satisfies that 3K = n - 1. Since the subtree of k(T) derived from transforming a three-children star has height of 2, the height of [T.sup.[DELTA]] is 2K = 2 x ((n - 1)/3) = 2(n - 1)/3.

ALGORITHM 1: SUB.

Input: a binary tree B rooted at s;

Output: an optimal solution of p-CLP on B and F[s][s][p];

Step 0. Use DFS based algorithm in [24] to traverse B, and record
  the parent node of every node % of B;
Step 1. for k from 1 up to h do
Use [absolute value of V(B(k))] processors to work simultaneously
  and all processors do the same work as follows for all
  x [member of] V(B(k)):
  if % is a leaf node then
  Use DFS based algorithm in [24] to compute c(x, y) and initialize
  F[x][y][1] [left arrow] 0, F[x][y][0] [left arrow] w(x) x c(x, y)
  for any y [member of] n(s, x);
Step 2. for k from 1 up to h do
  Use [absolute value of V(B(k))] processors to work simultaneously
  and all processors do the same work as follows for all
  x [member of] V(B(k)):
  if x is a nonleaf node then
    for each q from 0 up to p do
      if 0 [less than or equal to] q [less than or equal to]
      min{p, [absolute value of V(BX)]} then
        Use DFS based algorithm in [24] to compute c(x, y) and
          then compute B[x][y][q] by (6) for any y [member of]
          n(s, x);


Therefore, we obtain [absolute value of [V.sub.b]] = n + ((5/3)n - 11/3) = (8/3)n-(11/3) in the worst case and conclude that BINY spends O(n) time to transform T into b(T).

Theorem 5. CLP in a general tree T is equivalent to CLP in b(T).

Proof. This theorem is equivalent to the proposition that no cache is located at one dummy node in any optimal solution to CLP in b(T). Suppose that a cache is located at a dummy node [alpha] in an optimal solution L and [alpha] is added by transforming star(x) by BINY. The cost of a new solution L' obtained by replacing [alpha] with x into L is less than the cost of L. This causes a contradiction.

The binary tree obtained by applying Tamir's algorithm [15] to a general tree T with n nodes has a height of at most n - 2, while one obtained by applying BINY to T has a height of at most 2(n - 1)/3. In terms of height of binary tree, BINY is superior to Tamir's algorithm. This will help to reduce the running time of algorithm SUB (Algorithm 1) shown in Section 3.3.

3.3. Algorithm for CLP on Trees. By Theorem 5, we only need to discuss CLP on binary trees. Let B be a binary tree and s the server (root) node, and let V(x) denote the node set of B or its subtree. For any node x of B, we let [B.sub.x] denote the subtree of B rooted at x. Let [x.sub.l] and [x.sub.r] be the left child and right child of x, respectively, and then let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the subtree of [B.sub.x] rooted at [x.sub.t] (resp. xr). We use h to denote the height of B and 1, 2, ..., h to label the levels of B bottom-up, and we use B(k) to denote the kth level of B. Let F[x][y][q] denote the minimum cost of the subproblem of p-CLP on [B.sub.x] when the closest cache to x on [pi](x, s) is located at y and q caches are placed in [B.sub.x]. Similar to the idea of solving the p-proxy problem in [18], we propose our way of computing F[x][y][q] and giving a new proof, shown in Theorem 6.

Theorem 6. For each node x of B other than leaves, each node y on [pi](x, s), and each 0 [less than or equal to] q [less than or equal to] min{p, [absolute value of V(BX)]}, one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Proof. For any node x of B, we need to consider whether a cache is located at x or not when discussing the subproblem of p-CLP on [B.sub.x].

(1) If a cache is located at x, then x needs no paying for its overall demand. So, the cost of the subproblem of p-CLP on [B.sub.x] is equal to the sum of that on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and that on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When the closest cache to x on [pi](s, x) is located at y, we observe that x is the closest cache on n(s, x) to [x.sub.l] and [x.sub.r]. The possible number q of caches placed in [B.sub.x] is at most p while at most [absolute value of V([B.sub.x])]. The number [q.sub.l] of caches in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] plus the number [q.sub.r] of caches in [B.sub.x] is equal to q - 1. The key work is to find the optimal ([q.sub.i], [q.sub.r])-CAS with [q.sub.l] + [q.sub.r] = q - 1, from which the cost of the subproblem of p-CLP on [B.sub.x] results is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

(2) If no cache is located at x, then the cost of x paying for its overall demand is w(x) x c(x, y). So, the cost of the subproblem of p-CLP on Bx is equal to the sum of that on Bx and that on Bx and the cost of x. When the closest cache to x on [pi](s, x) is located at y, we see that y is also the closest cache on n(s, x) to [x.sub.l] and [x.sub.r]. As discussed above, q [less than or equal to] min{p, [absolute value of V(BX)]}. The number [q.sub.l] of caches in [B.sub.x] plus the number [q.sub.r] of caches in [??] is equal to q. The key work is to find the optimal ([q.sub.l], [q.sub.r])-CAS with [q.sub.l] + [q.sub.r] = q, from which the cost of the subproblem of p-CLP on [B.sub.x] results is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Obviously, thecaseof q < 0 is forbidden. Let F[x][y][q] = [infinity], [for all]q < 0 for each node x of B and each node y on n(s, x). From the definition of F[x][y][q], we know that F[s][s][p] is just the minimum cost of p-CLP. Initially, we set F[x][y][0] = w(x) x c(x, y) and F[x][y][1] = 0 for each leaf node x of B and each node y on [pi](s, x).

We can first use the depth-first search (DFS) based algorithm in [24] to traverse B, by which we can record the parent node of every node x (thus record [pi](s,x) step by step) and compute the cost of path connecting any node and its ancestor. Based on Theorem 6 and above discussions, we devise a bottom-up dynamic programming algorithm, which can be described as a parallel algorithm SUB by using the techniques in [25].

Theorem 7. Given any binary tree B with n nodes and a height of h, SUB runs in O([ph.sup.2] + n) time for computing p-CLP on B.

Proof. Step 0 uses DFS based algorithm in [24] to traverse B, which runs O(n) time. In Step 1, for each level k = 1, 2, ..., h, the processor at every leaf node x [member of] V(B(k)) uses the algorithm in [24] to make initialization for each y [member of] [pi](s, x), which takes O(h) time. So, Step 1 runs at most 0([h.sup.2]) time. In Step 2, for each level k = 1, 2, ..., h, the processor at every nonleaf node x [member of] V(B(k)) uses the algorithm in [24] to compute c(x, y) and then compute F[x][y][q] by (6) for every 0 [less than or equal to] q [less than or equal to] min {p, [absolute value of V([B.sub.x])]} and every y [member of] [pi](s, x), which takes at most O([p.sup.2]h) time. So, Step 2 runs at most O([p.sup.2][h.sup.2]) time. We can use the method in [15] to infer that the practical running time of Step 2 is O(p[h.sup.2]). Therefore, SUB runs in 0(p[h.sup.2] + n) time.

3.4. Algorithm for (p, 2)-CSOP CLP on General Graphs. Based on (5) and discussions therein, we can solve (p,2)-CSOP CLP on a general graph G by first computing C(T([s.sub.1]), [p.sub.1]) in T([s.sub.1]) and C(T([s.sub.2]), [p.sub.2]) in T([s.sub.2]) for any ([p.sub.1], [p.sub.2])-CAS with [p.sub.1] + [p.sub.2] = p and then determining an optimal ([p.sub.1], [p.sub.2])-CAS such that the sum of C(T([s.sub.1]), [p.sub.1]) and C(T([s.sub.2]), [p.sub.2]) is minimized. We discover that the output F[[s.sub.i]][[s.sub.i]][[p.sub.i]], i = 1, 2, of SUB is just the value of C(T([s.sub.1]), [p.sub.1]) when we apply SUB to T([s.sub.i]). This forms our algorithm for (p, 2)-CSOP CLP on a general graph, described as algorithm GLOB (Algorithm 2).

Suppose that T([s.sub.1]) has [n.sub.1] nodes and T([s.sub.2]) has [n.sub.2] nodes. Clearly, [n.sub.1] + [n.sub.2] = n. GLOB uses BINY to transform T([s.sub.1]) into b(T([s.sub.1])) and T([s.sub.2]) into b(T([s.sub.2])). From Theorem 4, we know that b(T([s.sub.1])), i = 1, 2, has at most (8/3)[n.sub.i] - 11/3 nodes including at most (5/3)[n.sub.i] - 11/3 dummy nodes and has a height of at most 2([n.sub.i] - 1)/3. Let hi denote the height of b(T([s.sub.i])). For any ([p.sub.1], [p.sub.2])-CAS with [p.sub.1] + [p.sub.2] = p, GLOB applies SUB to [p.sub.1]-CLP on b(T([s.sub.1])) and [p.sub.2]-CLP on b(T([s.sub.2])), respectively. It follows from Theorem 7 that the former takes at most 0([p.sub.1][h.sup.2.sub.1] + (8/3)[n.sub.1]) time and the latter takes at most 0([p.sub.2][h.sup.2.sub.2] + (8/3)[n.sub.2]) time. Therefore, the running time of GLOB is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Further, we take [h.sub.1] [less than or equal to] 2([n.sub.1] - 1)/3 and [h.sub.2] [less than or equal to] 2([n.sub.2] - 1)/3 into the above inequality to obtain that the running time of GLOB in the worst case is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Theorem 8. Given an undirected graph G = (V, E, w, c) with n nodes and two server nodes, GLOB runs in 0([p.sup.2] max {[h.sup.2.sub.1], [h.sup.2.sub.2]} + (8/3)np) time for (p,2)-CSOP CLP on G and runs in at most O((4/9)[p.sup.2][n.sup.2]) time in the worst case.

4. Generalization

In this section, we discuss the p-cache location problem with m identical servers under CSOP (abbreviated to (p, m)-CSOP CLP) on an undirected graph G = (V, E, w, c). Let S = {[s.sub.1], ..., [s.sub.m]} be a collection of m identical servers. Given any set [OMEGA] [subset] V\S, we let c(z, [OMEGA] [union] S) denote the cost of node z paying for its per demand and let f([OMEGA]) denote the total cost of all the nodes paying for their overall demand; that is, f([OMEGA]) = [[summation].sub.z [member of] v] w(z) c(z, [OMEGA] [union] S). The aim of (p, m)-CSOP CLP is to find p cache locations in G to minimize the total cost of all the nodes paying for their overall demand. In essence, (p, m)-CSOP CLP aims to find an optimal set [[OMEGA].sup.*] to minimize the value of f([OMEGA]); that is, f([[OMEGA].sup.*]) = [min.sub.[OMEGA] [subset] V\S] f([OMEGA]).

In (p, m)-CSOP CLP, every client connects to the closest server to itself via a shortest route and gets information from the closest cache on the route or server. Let V([s.sub.i]), 1 [less than or equal to] i [less than or equal to] m be the subset of nodes of G to which [s.sub.i] is the closest server. Let T([s.sub.i]), 1 [less than or equal to] i [less than or equal to] m denote the single-source shortest paths tree in G with [s.sub.i] as origin spanning V([s.sub.i]) and let [OMEGA]([s.sub.i]) denote the subset of caches placed in T([s.sub.i]). Hence, we can rewrite f([OMEGA]) to be

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

ALGORITHM 2: GLOB.

Input: T([s.sub.1]) and T([s.sub.2]) derived from G = (V, E, w, c)
  with [s.sub.1] and [s.sub.2];
Output: [[GAMMA].sup.*];

Step 0. Use BINY to transform T([s.sub.1]) into b(T([s.sub.1])) and
  T([s.sub.2]) into b(T([s.sub.2]));
Step 1. [DELTA] [left arrow] [infinity];
  for [p.sub.1] from 0 up to p do (then [p.sub.2] = p - [p.sub.1])
    Apply SUB to b(T([s.sub.i])), i = 1, 2 to obtain
      F[[s.sub.i]][[s.sub.i]][[p.sub.i]];
    C(b(T([s.sub.i])), [p.sub.i]) [left arrow]
      F[[s.sub.i]][[s.sub.i]][[p.sub.i]];
    if C(b(T([s.sub.1])), [p.sub.1]) + C(b(T([s.sub.2])), [p.sub.2])
      < [DELTA] then
      [ALPHA] [left arrow] C(b(T([s.sub.1])), [p.sub.1]) +
      C(b(T([s.sub.2])), [p.sub.2]);
      [[GAMMA].sup.*]([s.sub.1]) [left arrow] [GAMMA]([s.sub.1]),
        [[GAMMA].sup.*]([s.sub.2]) [left arrow] [GAMMA]([s.sub.2]);
Step 2. [[GAMMA].sup.*] [left arrow] [[GAMMA].sup.*]([s.sub.1])
 [union] [[GAMMA].sup.*]([s.sub.2]);


Let [p.sub.i] be the number of caches in H(sf). Let [??] = ([p.sub.i], [p.sub.2], ..., [p.sub.m]) with [[summation].sup.m.sub.i=1] [p.sub.i] = P' Such a combination of Q(si), 1 < i < m having pf caches is denoted as p-CAS. Thus, (p, m)-CSOP CLP consists of m CLPs when m servers are placed at m predesignated locations of G. For any p-CAS, (p, m)-CSOP CLP consists of m subproblems; that is, pf-CLP in T([s.sub.i]), 1 [less than or equal to] i [less than or equal to] m. Let C(G, p) denote the minimum cost of (p, m)-CSOP CLP on G and let C(T([s.sub.i]), [p.sub.i]), 1 [less than or equal to] i [less than or equal to] m denote the minimum cost of [p.sub.i]-CLP in T(st). Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

Based on (12), for any [??]-CAS with [[summation].sup.m.sub.i=1] [p.sub.i] = p, we can solve (p, m)-CSOP CLP on G by first computing C(T([s.sub.i]), [p.sub.i]) in T([s.sub.i]) for every 1 [less than or equal to] i [less than or equal to] m and then determining an optimal [??]-CAS such that the sum of C(T([s.sub.i]), [p.sub.i]), 1 [less than or equal to] i [less than or equal to] m, is minimized. This idea can be described as algorithm EXTD.

Lemma 9. The number of [??]-CASs in (p, m)-CSOP CLP is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. The problem of allocating p caches to m distinct subtrees can be reduced to the model of putting p same balls into m distinct boxes. We first draw p + m - 1 dots one by one in a line and then select p dots to place balls and the other m - 1 dots to place baffles. The line is partitioned into m sections (boxes) by these m - 1 baffles together with two immaterial baffles at two ends of the line. There are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ways in all to partition the line into m boxes. Every way of partitioning the line produces a [??]-CAS. Therefore, (p, m)-CSOP CLP contains [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For any [??]-CAS with [[summation].sup.m.sub.i=1] [p.sub.i] = p, the combination of Theorems 7 and 4 yields that the running time of EXTD solving all [p.sub.i]-CLP in T([s.sub.i]), 1 [less than or equal to] i [less than or equal to] m, is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

By Lemma 9, we conclude that the running time of EXTD is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

From [h.sub.i] [less than or equal to] 2([n.sub.i] - 1)/3, [i.sub.n] [less than or equal to] n + 1 - m for every 1 [less than or equal to] i [less than or equal to] m, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

Obviously, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)

We take (15) and (16) into (14) to obtain that the running time of EXTD in the worst case is at most O((4/9)[(n - m).sup.2]([(m + p).sup.p]/(p - 1)!)).

Theorem 10. Given an undirected graph G = (V, E, w, c) with n nodes and m servers, EXTD runs in O([m.sup.p](p x [max.sub.1 [less than or equal to] i [less than or equal to] m] h2 + (8/3)n)) time for (p, m)-CSOP CLP on G and runs in at most 0((4/9)[(n - m).sup.2]((m + p)p/(p - 1)!)) time in the worst case.

5. Numerical Experiments

5.1. An Illustrative Example. In this subsection, we first give an example to illustrate our algorithm GLOB for computing (p, 2)-CSOP CLP. Considering that (p, 2)-CSOP CLP on a general network can be reduced to that on a corresponding tree network, we select a tree network as our example for ease of illustration, shown in Figure 1. The example tree T has 25 client nodes labelled by [u.sub.1], [u.sub.2], ..., [u.sub.25] and two server nodes labelled by [s.sub.1] and [s.sub.2]. The number wk, 1 < k < 25, on client node [u.sub.k] represents the demand account of [u.sub.k], and the number on every edge represents the cost of one node paying for its per demand. For instance, the demand account of [u.sub.5] is 0.76, and the total cost of [u.sub.5] paying for its overall demand is 1.55 x 0.76 = 1.1780.

First, we make preparation works. The unique path [PI][[s.sub.1], [s.sub.2]] of T connecting [s.sub.1] and [s.sub.2] is [s.sub.1][u.sub.14][u.sub.18][u.sub.19][u.sub.15][s.sub.2]. It is easy to see that [u.sub.14] and [u.sub.18] are closer to [s.sub.1] than [s.sub.2] while [u.sub.19] and [u.sub.15] are closer to [s.sub.2] than [s.sub.1]. Thus, N([s.sub.1]) = {[s.sub.1], [u.sub.14], [u.sub.18]} and N([s.sub.1]) = {[u.sub.19], [u.sub.15], [s.sub.2]}. Based on Lemma 2, we use the DFS based approach to obtain T([s.sub.1]) and T([s.sub.2]), shown in the left subfigure of Figure 2 and the left subfigure of Figure 3, respectively. Both the heights of T([s.sub.1]) and T([s.sub.2]) are three. We apply BINY to transform T([s.sub.1]) into a binary tree b(T([s.sub.i])) shown in the right subfigure of Figure 2, where eight dummy nodes added by BINY are labelled by [d.sub.1], [d.sub.2], ..., [d.sub.8]. Similarly, we obtain b(T([s.sub.2])) shown in the right subfigure of Figure 3, where nine dummy nodes are labelled by [d.sub.1], [d.sub.2], ..., [d.sub.9]. All the dummy nodes have a weight of zero and all the edges between a dummy node and its parent node have a weight of zero. Both the height of T([s.sub.1]) and T([s.sub.2]) are five.

Next, we use GLOB to solve (p, 2)-CSOP CLP on T. Set p = 4 and p = 5 as examples. For any ([p.sub.1], [p.sub.2])-CAS with [p.sub.1] + [p.sub.2] = 4, GLOB computes the minimum cost C(T([s.sub.1]), [p.sub.1]) of [p.sub.1]-CLP in T([s.sub.1]) and the set [[GAMMA].sup.*.sub.1]([s.sub.1]) of cache locations and the minimum cost C(T([s.sub.2]), [p.sub.2]) of [p.sub.2]-CLP in T([s.sub.2]) and [[GAMMA].sup.*.sub.1] ([s.sub.2]). The data are listed in Table 1.Clearly, the optimal value C(T,4) of (4,2)-CSOP CLP on T is 33.2950, and thus the optimal set [[GAMMA].sup.*.sub.1] of cache locations is {[u.sub.8], [u.sub.17], [u.sub.18], [u.sub.20]}. Similarly, the data output by GLOB for any ([p.sub.1], [p.sub.2])-CAS with [p.sub.1] + [p.sub.2] = 5 are listed in Table 2. Clearly, the optimal value C(T, 5) of (5,2)-CSOP CLP on T is 27.7770, and thus the optimal set [[GAMMA].sup.*.sub.2] is {[u.sub.5], [u.sub.8], [u.sub.17], [u.sub.18], [u.sub.20]}.

5.2. Comparison of Running Times. In this subsection, we make a large number of numerical experiments to compare the running times of our algorithm GLOB and EXTD, respectively. In view of the fact that (p, m)-CSOP CLP with m [greater than or equal to] 2 on a general graph can be reduced to multiple CLPs on binary trees, we select a series of complete binary trees as examples for ease of comparison. All the binary trees are generated randomly and have almost same number of nodes. We build a centralized parallel computer system (i.e., a star network with one central computer and five parallel computers) by connecting six identical PCs equipped with 2 GB RAM and Intel core i5 CPU using a Windows 7 operating system. Our numerical experiments were carried out on this computer system.

For (p, 2)-CSOP CLP, we consider different inputs of n and p: n = 100, 102, 104,..., 200 and 2 [less than or equal to] p [less than or equal to] 20. All the binary trees we select have odd nodes. Given n = 200 and p = 20, there are 100 different combinations of [n.sub.1] and [n.sub.2]; that is, [n.sub.1] = 1, 3, 5, ..., 199 and [n.sub.2] = 200 - [n.sub.1]. All the running times of GLOB for 100 combinations are depicted in Figure 4(a). Given any combination of n and p, we record the average running time of 100 combinations. In Figure 4(b), all the average times for the combinations of n and fixed p are depicted, for any given p = 5, 10, 15, 20. In Figure 4(c), all the average times for the combinations of p and fixed n are depicted, for any given n = 100, 120, 140, 160, 180, 200. In Figure 4(d), all the average times for the combinations of n and p are depicted.

For (p, m)-CSOP CLP, we are given n = 200 or 201 and consider different inputs of m and p: 2 [less than or equal to] m [less than or equal to] 5 and 2 [less than or equal to] p [less than or equal to] 20. All the binary trees we select have odd nodes. Given m = 5 and p = 20, there are 10626 different CAS's. All the running times of EXTD for 10626 CAS's are depicted in Figure 5(a). Given any combination of m and p, we record the average running time of 10626 CAS's. In Figure 5(b), all the average times for the combinations of m and fixed p are depicted, for any given p = 5, 10, 15, 20. In Figure 4(c), all the average times for the combinations of p and fixed m are depicted, for any m = 2, 3, 4, 5. In Figure 5(d), all the average times for the combinations of m and p are depicted.

Next, we present the running times of EXTD for different inputs of n. Given m = 5, we consider six different combinations of p = 20, 22, 24, 26, 28, 30 and fixed m = 5. In Figure 6(a), all the average times for n = 205 + 30x(i -1), 1 [less than or equal to] i [less than or equal to] 5, are depicted. Also, we depict all the average times for the combinations of n and p in Figure 6(b). Note that every complete binary tree has 41 + 6 x (i - 1) nodes. Given p = 30, we consider four different combinations of m = 2, 3, 4, 5 and fixed p = 30. In Figure 6(c), all the average times for exactly or approximately n = 205 + 30x(i - 1), 1 [less than or equal to] i [less than or equal to] 5 are depicted. In Figure 6(d), all the average times for the combinations of n and m are depicted.

6. Conclusions

In this paper, we presented an efficient algorithm GLOB for (p, 2)-CSOP CLP and EXTD for (p, m)-CSOP CLP based on a fast parallel algorithm for CLP, respectively. GLOB runs in a polynomial time while EXTD applies to the cases of not too large p and m in general. Fortunately, both m and p are not so large in practice that the running time of EXTD becomes intolerable with n increasing fast. Therefore, we think that EXTD will have extensive applications.

Every cache involved in this paper is identical to server; that is, every cache has the same contents as server. However, a cache sometimes only contains one part of contents. Suppose that every cache contains [rho]% contents of server. Under CSOP, each node connects to the closest server to itself via a shortest route. On average, each node has [rho]% demand provided by the closest cache on the route and (1 - [rho])% demand provided by the server. Hence, the cost of node z paying for its overall demand is equal to [rho]% x c(z, [OMEGA]([s.sub.i]) [union] {[s.sub.i]}) + (1 - [rho]%) x c(z, [s.sub.i]). Let g([OMEGA]) denote the total cost of all the nodes paying for their overall demand. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)

This version of (p, m)-CSOP CLP aims to find an optimal set [[OMEGA].sup.*] such that g([OMEGA]) is minimized. The problem remains as one future research topic.

http://dx.doi.org/10.1155/2014/586146

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] M. Baentsch, L. Baum, G. Molter, S. Rothkugel, and P. Sturm, "World wide web caching: the application-level view of the internet," IEEE Communications Magazine, vol. 35, no. 6, pp. 170-178, 1997.

[2] P. Danzig, R. Hall, and M. Schwartz, "A case for caching file objects inside internetworks," ACM SIGCOMM Computer Communication Review, vol. 23, no. 4, pp. 239-248, 1993.

[3] S. Glassman, "A caching relay for the World Wide Web," Computer Networks and ISDN Systems, vol. 27, no. 2, pp. 165-173, 1994.

[4] N. Yeager and R. McGrath, Web Server Technology: The Advanced Guide for World Wide Web Information Providers, Morgan Kaufmann Publishers, San Francisco, Calif, USA, 1996.

[5] A. Chankhunthod, P. Danzig, C. Neerdaels, M. Schwartz, and K. Worrell, "A hierarchical internet object cache," in Proceedings of the Annual Conference on USENIX Annual Technical Conference (ATEC '96), p. 13, USENIX Association, Berkeley, Calif, USA, 1996.

[6] E. Cohen, B. Krishnamurthy, and J. Rexford, "Improving end-to-end performance of the Web using server volumes and proxy filters," Computer Communication Review, vol. 28, no. 4, pp. 241-253, 1998.

[7] M. Abrams, C. Stanridge, G. Abdulla, E. Fox, and S. Williams, "Removal policies in network caches for World-Wide Web documents," ACM SIGCOMM Computer Communication Review, vol. 26, no. 4, pp. 293-305, 1996.

[8] P. Krishnan, "Utility of co-operating Web proxy caches," Computer Networks and ISDN Systems, vol. 30, no. 1-7, pp. 195-203, 1998.

[9] R. Malpani, J. Lorch, and D. Berger, "Making world wide web caching servers cooperate," in Proceedings of the 4th International World-Wide Web Conference, pp. 107-117, Boston, Mass, USA, December 1995.

[10] A. Heddaya and S. Mirdad, "WebWave: globally load balanced fully distributed caching of hot published documents," in Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), pp. 160-168, Baltimore, Md, USA, May 1997

[11] P. Krishnan, D. Raz, and Y. Shavitt, "The cache location problem," IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 568-582, 2000.

[12] B. Li, X. Deng, M. Golin, and K. Soharby, "On the optimal placement of Web proxies in the Internet: linear topology," in Proceedings of the IFIP TC-6 8th International Conference on High Performance Networking (HPN '98), pp. 485-495, Vienna, Austria, September 1998.

[13] B. Li, M. J. Golin, G. F. Italiano, X. Deng, and K. Sohraby, "On the optimal placement of web proxies in the Internet," in Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societie (INFOCOM '99), pp. 1282-1290, New York, NY, USA, March 1999.

[14] O. Kariv and S. L. Hakimi, "An Algorithmic Approach to Network Location Problems. II: the p-Medians," SIAM Journal on Applied Mathematics, vol. 37, no. 3, pp. 539-560, 1979.

[15] A. Tamir, "An O(pn2) algorithm for the p-median and related problems on tree graphs," Operations Research Letters, vol. 19, no. 2, pp. 59-64, 1996.

[16] G. J. Woeginger, "Monge strikes again: optimal placement of web proxies in the internet," Operations Research Letters, vol. 27, no. 3, pp. 93-96, 2000.

[17] G. Chen, G. Zhang, and W. Ding, "Web proxylocation problem in the tree networks," Applied Mathematics A: Journal of Chinese Universities, vol. 19, pp. 510-514, 2004 (Chinese).

[18] G. Chen, G. Zhang, and R. E. Burkard, "The web proxy location problem in general tree of rings networks," Journal of Combinatorial Optimization, vol. 12, no. 4, pp. 327-336, 2006.

[19] D. Du, "Placement of read-write Web proxies in the Internet," in Proceedings of the The 21st International Conference on Distributed Computing Systems (ICDCS '01), pp. 687-687, Phoenix, Ariz, USA, April 2001.

[20] X. Jia, D. Li, X. Hu, W. Wu, and D. Du, "Placement of Web-server proxies with consideration of read and update operations on the Internet," Computer Journal, vol. 46, no. 4, pp. 378-390, 2003.

[21] J. Liu and J. Yang, "Delay-constrained Web proxy problem in Internet," Computer Engineering and Applications, vol. 45, no. 31, pp. 109-110, 2009.

[22] J. A. Bondy and U. S. R. Murty, Graph Theory with Application, Macmillan, London, UK, 1976.

[23] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269-271, 1959.

[24] W. Ding, Y. Zhou, G. Chen, H. Wang, and G. Wang, "On the 2MRS problem in a tree with unreliable edges," Journal of Applied Mathematics, vol. 2013, Article ID 743908,11 pages, 2013.

[25] W. Ding and G. Xue, "A fast parallel algorithm for finding a most reliable source on a general ring-tree graph with unreliable edges," in Combinatorial Optimization and Applications, vol. 6831 of Lecture Notes in Computer Science, pp. 98-112, Springer, Heidelberg, Germany, 2011.

Hongfa Wang and Wei Ding

Zhejiang University of Water Resources and Electric Power, Hangzhou, Zhejiang 310018, China

Correspondence should be addressed to Wei Ding; dingweicumt@163.com

Received 16 February 2014; Revised 20 June 2014; Accepted 4 August 2014; Published 24 August 2014

Academic Editor: Qi Cheng

TABLE 1: Major data output by GLOB for (4,2)-CSOP CLP on T.

[p.sub.1]   [[gamma].sup.*.sub.1]   C(T([s.sub.1]),
                 ([s.sub.1])          [p.sub.1])

0                                       37.2100
1                [u.sub.17]             273100
2                [u.sub.17],            19.9150
                 [u.sub.18]
3                [u.sub.5],             14.3970
                 [u.sub.17],
                 [u.sub.18]
4                [u.sub.5],             12.4170
                 [u.sub.13],
                 [u.sub.17],
                 [u.sub.18]

[p.sub.2]   [[gamma].sup.*.sub.2]   C(T([s.sub.2]),   Total cost
                 ([s.sub.2])          [p.sub.2])

4                [u.sub.3],             8.5600         45.7700
                 [u.sub.8],
                 [u.sub.15],
                 [u.sub.20]
3                [u.sub.8],             10.6600        37.9700
                 [u.sub.15],
                 [u.sub.20]
2                [u.sub.8],             13.3800        33.2950
                 [u.sub.20]
1                 [u.sub.8]             19.0350        33.4320
0                                       30.1050        42.5220

TABLE 2: Major data output by GLOB for (5,2)-CSOP CLP on T.

[p.sub.1]    [[GAMMA].sup.*.sub.1]    C(T([s.sub.1]),
                  ([s.sub.1])           [p.sub.1])

0                                         37.2100

1                 [u.sub.17]              27.3100

2           [u.sub.17], [u.sub.18]        19.9150

3           [u.sub.5], [u.sub.17],        14.3970
                  [u.sub.18]

4           [u.sub.5], [u.sub.13],        12.4170
            [u.sub.17], [u.sub.18]

5            [u.sub.1], [u.sub.5],        10.5895
            [u.sub.13], [u.sub.17],
                  [u.sub.18]

[p.sub.2]    [[GAMMA].sup.*.sub.2]    C(T([s.sub.2]),    total
                  ([s.sub.2])           [p.sub.2])       cost

5            [u.sub.3], [u.sub.4],         6.7400       43.9500
            [u.sub.8], [u.sub.15],
                  [u.sub.20]

4            [u.sub.3], [u.sub.8],         8.5600       35.8700
            [u.sub.15], [u.sub.20]

3           [u.sub.8], [u.sub.15],        10.6600       30.5750
                  [u.sub.20]

2            [u.sub.8], [u.sub.20]        13.3800       27.7770

1                  [u.sub.8]              19.0350       31.4520

0                                         30.1050       40.6945
COPYRIGHT 2014 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Wang, Hongfa; Ding, Wei
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2014
Words:9064
Previous Article:A least squares method for variance estimation in heteroscedastic nonparametric regression.
Next Article:A physically based runoff model analysis of the Queretaro river basin.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters