We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (ML k FL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k ≥ 0. Assigning client j to a facility f incurs a connection cost d ( f , j ). The goal is to open a set F ⊆ F of k facilities and assign each client j to a facility f ( j )∈ F so as to minimize max f ∈ F ∑ j ∈ C : f ( j )= f d ( f , j ); we call ∑ j ∈ C : f ( j )= f d ( f , j ) the load of facility f . This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for ML k FL for when F = C . ML k FL is rather poorly understood, and only an O ( k )-approximation is currently known for ML k FL, even for line metrics . Our main result is the first polytime approximation scheme (PTAS) for ML k FL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that ML k FL is strongly NP -hard on line metrics. We also devise a quasi-PTAS for ML k FL on tree metrics. ML k FL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k -median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack ML k FL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and argue that a MILP-solution minimizing a certain potential function possesses the desired structure and then use a rounding algorithm for the generalized-assignment problem to “transfer” this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facility-location problems. For instance, we show that: (a) even a configuration-style LP-relaxation has a bad integrality gap; and (b) a multi-swap k-median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding the problem, and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

In this paper, we present two approximation algorithms for minimizing power consumption of wireless sensor networks (WSNs) in environmental monitoring applications. Most approximation algorithms for similar problems assume that the cost function satisfies the triangle inequality. For a cost function defined based on power consumption for reliable transmission between two nodes in a WSN, this assumption is not true. We first prove that we have the triangle inequality in a relaxed sense for these cost functions and then we use this in performance analysis of our two algorithms. The first algorithm is a natural bottom-up algorithm, while the second algorithm is a more complicated, top-down algorithm. We show that the solutions from both these algorithms are within a constant factor of the optimum value, and that the top-down algorithm has a better constant ratio. Our experimental results show that these two algorithms usually perform much better than proven approximation guarantees.

In this paper, we present two approximation algorithms for near-optimal design of hierarchical wireless sensor networks (WSNs) in environmental monitoring applications. Since the problem of our interest is NP-hard, we design two approximation algorithms for this problem. The first algorithm is a natural bottom-up algorithm that uses an approximation algorithm of the k-median problem with approximation ratio ρ. The second algorithm is a less obvious, top-down algorithm that also uses the same ρ-approximation algorithm. We show that the bottom-up algorithm is a ((ρ + 1)p- 1)-approximation algorithm, where p is the number of levels in the hierarchy, while the top-down algorithm is a 3ρ- approximation. That is, the performance of the top-down algorithm does not depend on p. Our experimental results show that these two algorithms perform very well, with the top-down algorithm being superior.

In recent years, global and grid computing emerge as two powerful technology trends. In this paper, we compare these two approaches of distributed computing. First, we present a definition for global computing that accentuates the key point in this trend. This key point distinguishes global computing from other trends and covers many such systems. Second, we contrast two approaches in general characteristics. Then, by comparing them in technical issues, we show that the key point in our definition of global computing is the main source of many technical differences between these methods. Finally, we present our opinion about the probable future of global and grid computing