We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job's arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and providing a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio $8(2p-1)/p < 16$ when all jobs have uniform length $p$.

The rapid development of the Real-Time and Embedded System (RTES) has increased the requirement on the processing capabilities of sensors, mobiles and smart devices, etc. Meanwhile, energy efficiency techniques are in desperate need as most devices in RTES are battery powered. Following the above trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The problem complexity analysis for different task and system models is also presented. Experimental results show that the proposed approximation scheme performs close to the optimal solution in average.

In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).

The rapid development of the Internet of Things (IoT) has increased the requirement on the processing capabilities of sensors, mobile phones and smart devices. Meanwhile, energy efficiency techniques are in desperate need as most devices in the IoT systems are battery powered. Following the above two trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The complexity analysis of the problem for different task and system models is also presented. Experimental results show that the proposed approximation algorithm performs close to the optimal solution in average.

We study the problem of assigning transmission power to the nodes of ad hoc wireless networks to minimize power consumption while ensuring that the given source reaches all the nodes in the network (unidirectional links allowed for broadcast). In the most general cost model, the best published approximation ratio is achieved by the "greedy spider" algorithm (Calinescu et al., ESA 2003). We present a variant of this algorithm with running time big-Oh of n to power 3 (n is the number of nodes), and the same approximation ratio. In the restricted "Euclidean" two-dimensional cost model, where the power requirement to transmit from node u to node v is the Euclidean distance between the location of u and the location v, raised to a fixed power that dependends on the wireless environment, the best known approximation ratio is achieved by the "relative greedy" algorithm (Caragiannis et al., ICALP 2007). We present a variant of this algorithm with running time big-Oh of n times m (m is the number of edges in the input graph), and the same approximation ratio. The new variants make use of advanced data structures and/or simple amortized analysis, improving naive variants by a factor of n. This improvement allows us to apply these algorithms to large instances (1000-2000 nodes). Our experimental results show that the best output achievable within 100 seconds improves the solution based on minimum spanning tree by an average of up to 15%, and comes within 25% of optimum, in average, on the instances where we can compute the optimum (based on an integer program). The improvement is circa 50% larger compared to what one would get applying existing fast heuristics.

Given a directed simple graph $G=(V,E)$ and a cost function $c:E \rightarrow R_+$, the power of a vertex $u$ in a directed spanning subgraph $H$ is given by $p_H(u) = \max_{uv \in E(H)} c(uv)$, and corresponds to the energy consumption required for wireless node $u$ to transmit to all nodes $v$ with $uv \in E(H)$. The power of $H$ is given by $p(H) = \sum_{u \in V} p_H(u)$. Power Assignment seeks to minimize $p(H)$ while $H$ satisfies some connectivity constraint. In this paper, we assume $E$ is bidirected (for every directed edge $e \in E$, the opposite edge exists and has the same cost), while $H$ is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that a bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In 2010, we introduced a greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the algorithm's analysis to 1.85, combining techniques from Robins and Zelikovsky in 2000 for Steiner Tree, and Caragiannis, Flammini, and Moscardelli in 2007 for the broadcast version of Power Assignment, together with a simple idea inspired by Byrka and coworkers in 2010. The proof also shows that a natural linear programming relaxation, introduced by Calinescu and Qiao in 2012, has integrality gap at most 1.85.

We study the problem of assigning transmission power to the nodes of ad hoc wireless networks to minimize power consumption while ensuring strong network connectivity (unidirectional links allowed). We give (1) an exact algorithm based on new integer linear program formulations, solving instances with up to 30 nodes in one minute, (2) a fast variant of a recent greedy approximation algorithm, finishing within 85 seconds on instances with up to 2000 nodes, (3) a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms, showing tradeoffs between the running time and the quality of the output. Thus we deal with the original power assignment problem introduced by Chen and Huang in 1989, who proved that a minimum spanning tree (MST) based approximation algorithm has ratio of 2. Our experimental results show that the recent 1.98-approximation algorithm improves the MST solution by an average of up to 15%, and comes within 4-16% of optimum, in average, on the instances where we can compute the optimum.

In this paper we consider the problem of routing traffic between k source-destination pairs. Using game theoretic modeling we provide randomized strategies to minimize the threat of attacks on links by an adversary. The adversary is assumed to have a choice of c edges for attack. We propose iterative methods to find the Nash Equilibrium of the zero-sum game. The proposed schemes have been implemented using existing network models (GEANT in Europe and the AT&T network in US) and show marked reduction in the gain of the attacker. As the gain of the attacker is related to the congestion on the edges, our schemes also reduce congestion.

Let $f:2^X \rightarrow \cal R_+$ be a monotone submodular set function, and let $(X,\cal I)$ be a matroid. We consider the problem ${\rm max}_{S \in \cal I} f(S)$. It is known that the greedy algorithm yields a $1/2$-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73–87] for this problem. For certain special cases, e.g., ${\rm max}_{|S| \leq k} f(S)$, the greedy algorithm yields a $(1-1/e)$-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning $f(S)$ for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177–188] and for explicitly posed instances assuming $P \neq NP$ [U. Feige, J. ACM, 45 (1998), pp. 634–652]. In this paper, we provide a randomized $(1-1/e)$-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307–328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the $38$th ACM Symposium on Theory of Computing, 2008, pp. 67–74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires $|X|$ to be exponential in the original problem size, we are able to achieve a $(1-1/e-o(1))$-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.

We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity B of available resource. We show that this NP-hard Resource Allocation problem can be (1/2 − ε)-approximated in randomized polynomial time, which improves upon earlier approximation results.

In this paper we address the issue of designing multi-path routing algorithms. Multi-path routing has the potential of improving the throughput but requires buffers at the destination. Our model assumes a network with capacitated edges and a delay function associated with the network links (edges). We consider the problem of establishing a specified throughput from source to destination in the network, given bounds on the buffer size available at the destination and a bound on the maximum delay paths are allowed to have. A related problem which we consider is to establish bounds on the delay variance (which we call jitter) amongst the paths chosen for the multi-path routing scheme. We show that the problems are NP-complete and present pseudo-polynomial algorithms based on linear programming. We also propose practical heuristics and present the experimental results on an existing network topology. The results are promising.

In this paper, we study theInterference-Aware Broadcast Scheduling problem, whereall nodes in the Euclidean plane have a transmission range and an interference range equal to r and alpha times r, for alpha at least 1, respectively. Minimizing latency is known to be NP-Hard even when alpha equals 1. The network radius D, the maximum graph distance from the source to any node, is also known to be a lower bound. We formulate the problem as Integer Programs (IP) and optimally solve moderate-size instances. We also propose six variations of heuristics, which require no pre-processesing of inputs, based on the number of receivers gained by each additional simultaneous broadcasting node. The experimental results show that the best heuristics give the solutions only 13-20% exceeding the optimum solutions. Further, an O(alpha D) schedule is proven to exist yielding an O(alpha) approximation algorithm.

Let G be a connected graph, and let V and $V'$ be two n-element subsets of its vertex set $V(G)$. Imagine that we place a chip at each element of V and we want to move them into the positions of $V'$ (V and $V'$ may have common elements). A move is defined as shifting a chip from $v_1$ to $v_2$ ($v_1,v_2 \in V(G)$) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.

It is desirable to allow packets with the same source and destination to take more than one possible path. This facility can be used to ease congestion and overcome node failures. One approach toward deploying multipath routing in the networks is by creating virtual paths, e.g. using MPLS. There are however costs associated with establishing and maintaining such virtual connections. In this paper, we present the formulation and an approximate solution for the problem of modeling, creation and optimization of the multiple paths in the networks. The aim is to minimize the cost of operating the network and maximize the utilization, using multiple paths. The polynomial-time approximation algorithm presented is based on mixed and linear programming formulation. This approximate solution has a constant approximation ratio; more precisely the throughput of the paths output by our algorithm is at least 0.14 of the optimum throughput, without exceeding the cost of the optimal solution.

Summary form only given. There have been papers indicating that the maximal ratio combiner device can result in energy savings in wireless ad hoc networks by using hitch-hiking. We study the min-energy broadcast with hitch-hiking problem, an idealized version of broadcast using hitch-hiking, a problem studied experimentally in the INFOCOM 2004 paper of Agarwal et al. min-energy broadcast with hitch-hiking captures the maximum savings one can achieve in broadcasting using maximal ratio combiners. We show that the optimum of the classical min-energy broadcast problem is at most O(log2n) times the optimum of min-energy broadcast with hitch-hiking, where n is the number of nodes in the networks. We show that this bound is tight up to a constant. Moreover, the same bounds hold for Unicast. In the special case when the nodes are on a line and the power requirement for node u to reach node v is d(u, v)K, where d(u, v) the Euclidean distance between u and v and k is the signal attenuation exponent, which is assumed to be in between 2 and 5, we show that the optimum of the min-energy broadcast problem is at most a constant times optimum of min-energy broadcast with hitch-hiking. A formal definition of min-energy broadcast with hitch-hiking is given below. The input consists of a complete directed graph G = (V, E) with power requirement function c : E rarr R+, and a source s epsi V. The output consists of a permutation tau =1, v2, ..., vn> of V with vn= s and power assignment p(v) of every vertex v. For every 1 les i les ii, vj) = p(vi)/c(vi)j). An output is feasible if for every j > 1 we have Sigmai = 1j - 1q(vivj) ges 1. The objective is to minimize Sigmai = 1np(vi)

Optimizing the energy consumption in monitoring and communication protocols for wireless sensor networks has become the most important performance objective. We explore the problem of maximizing sensor network lifetime, i.e., time during which the set of targets is covered. We propose centralized algorithms for lifetime maximization with provable approximation ratio for the realistic model studied. In this paper we introduce reliability requirement for distributed target-monitoring protocols and prove that previously considered protocols are reliable. A new deterministic energy-efficient protocol for sensor networks (DEEPS) aimed at prolonging lifetime is proposed. We prove that DEEPS is reliable and compare DEEPS with several known target-monitoring protocols in NS2 environment using LEACH (W. Heinzelman et al., 2000) for simulating monitoring data delivery to the base. Our contributions also include the first full-fledged simulation of the monitoring protocols on NS2 combined with LEACH (W. Heinzelman et al., 2000) as a communication protocol, and extensive experimental study of several protocols showing almost 2 times increase in the lifetime for DEEPS over known protocols

Recently, there have been papers indicating that the maximal ratio combiner device can result in energy savings in wireless ad hoc networks by using hitch-hiking. We study the min-energy broadcast with hitch-hiking problem, an idealized version of broadcast using hitch-hiking, a problem studied experimentally in the INFOCOM 2004 paper of Agarwal et al. min-energy broadcast with hitch-hiking captures the maximum savings one can achieve in broadcasting using maximal ratio combiners. We show that the optimum of the classical min-energy broadcast problem is at most O(log2n) times the optimum of min-energy broadcast with hitch-hiking, where n is the number of nodes in the networks. We show that this bound is tight up to a constant. In the special case when the nodes are on a line and the power requirement for node u to reach node v is d(u,v)Kwhere d(u,v) the Euclidean distance between u and v and K is the signal attenuation exponent, which is assumed to be in between 2 and 5, we show that the optimum of the min-energy broadcast problem is at most a constant times optimum of min-energy broadcast with hitch-hiking. We also show that min-energy broadcast with hitch-hiking is NP-Hard, and present approximation algorithms. A formal definition of min-energy broadcast with hitch-hiking is given below. The input consists of a complete directed graph G = (V, E) with power requirement function c: E rarr R+, and a source s isin V. The output consists of a permutation T =1, v2,...., vn> of V with v1= s and power assignment p(v) of every vertex v. For every 1 les iivj) = p(vi)/c(vivj). An output is feasible if for every j > 1 we have Sigmani=1p(vi)

Optimizing the energy consumption in wireless sensor networks has recently become the most important performance objective. We assume the sensor network model in which sensors can interchange idle and active modes. Given monitoring regions, battery life and energy consumption rate for each sensor, we formulate the problem of maximizing sensor network lifetime, i.e., time during which the monitored area is (partially or fully) covered. Our contributions include (1) an efficient data structure to represent the monitored area with at most n/sup 2/ points guaranteeing the full coverage which is superior to the previously used approach based on grid points, (2) efficient provably good centralized algorithms for sensor monitoring schedule maximizing the total lifetime including (1+ln(1-q)/sup -1/)-approximation algorithm for the case when a q-portion of the monitored area is required to cover, e.g., for the 90% area coverage our schedule guarantees to be at most 3.3 times shorter than the optimum, (4) a family of efficient distributed protocols with trade-off between communication and monitoring power consumption, (5) extensive experimental study of the proposed algorithms showing significant advantage in quality, scalability and flexibility.

Motivated by topology control in ad-hoc wireless networks, power assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). These problems have been studied in the past. In this paper we consider delay bounds as an additional constraint to provide quality of service. Delay is measured by the number of hops on a path between two nodes. We present an algorithm for minimum power bounded hops broadcast with guaranteed bicriteria ratio of (O(log n), O(log n)) for general graphs. That is, in the solution produced by our algorithm, the number of hops between the root and any other node is at most O(log n) times the given bound and the power is at most O(log n) times the power of optimal solution. Our bicriteria results extend to min-power bounded-hops strong connectivity (the solution must have a path of at most d edges in between any two nodes) and min-power bounded-hops symmetric connectivity (the undirected graph having an edge uv iff the solution has both uv and vu is required to have diameter at most d). Previous work for min-power bounded-hops strong connectivity consists only of constant or better approximation for special cases of the Euclidean case. We also provide better guarantees for the Euclidean cases by post processing solutions of the main algorithm.

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput.}, 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for {\sc 0-Extension}. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput.}, 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least $c \sqrt{\lg k}$ for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.

Wieselthier et al. (2000) proposed three greedy heuristics for Min-Power Asymmetric Broadcast Routing: SPT (shortest-path tree), MST (minimum spanning tree), and BIP (broadcasting incremental power). Wan et al. (2001) proved that SPT has an approximation ratio of at least (n/2) where n is the total number of nodes, and both MST and BIP have constant approximation ratios. Based on the approach of pruning, Wieselthier et al. also proposed three greedy heuristics for Min-Power Asymmetric Multicast Routing: P-SPT (pruned shortest-path tree), P-MST (pruned minimum spanning tree), and P-BIP (pruned broadcasting incremental power). In this paper, we first prove that the approximation ratios of these three heuristics are at least (n-1/2),n-1, and n-2-o(1), respectively. We then present constant-approxiation algorithms for Min-Power Asymmetric Multicast Routing. We show that any /spl rho/-approximation Steiner tree algorithm gives rise to a c/spl rho/-approximation heuristic for Min-Power Asymmetric Multicast Routing, where c is a constant between 6 and 12. In particular, the Takahashi-Matsuyama Steiner tree heuristic leads to a heuristic called SPF (shortest-path first), which has an approximation ratio of at most 2c. We also present another heuristic, called MIPF (minimum incremental path first), for Min-Power Asymmetric Multicast Routing and show that its approximation ratio is between (13/3) and 2c. Both SPF and MIPF can be regarded as an adaptation of MST and BIP, respectively, in a different manner than pruning. Finally, we prove that any /spl rho/-approximation Steiner tree algorithm also gives rise to a 2/spl rho/-approximation algorithm for Min-Power Symmetric Multicast Routing.

The QoS Steiner tree problem asks for the most cost-efficient way to multicast multimedia to a heterogeneous collection of users with different consumption rates. We assume that the cost of using a link is not constant, but rather depends on the maximum bandwidth routed through the link. Formally, given a graph with costs on the edges, a source node and a set of terminal nodes, each one with a bandwidth requirement, the goal is to find a Steiner tree containing the source and the cheapest assignment of bandwidth to each of its edges so that each source-to-terminal path in the tree has bandwidth at least as large as the bandwidth required by the terminal. Our main contributions are: (1) new covering-type integer linear program formulations for the problem; (2) two new heuristics based on the primal-dual framework; (3) a primal-dual constant-factor approximation algorithm; (4) an extensive experimental study of the new heuristics and of several previously proposed algorithms.

We study the problem of assigning transmission ranges to the nodes of ad hoc wireless networks to minimize power consumption while ensuring network connectivity. We give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35-40 nodes in 1 hour; a proof that min-power symmetric connectivity with asymmetric power requirements is inapproximable within factor (1 - /spl epsi/) ln |V| for any /spl epsi/ > 0 unless P = NP; an improved analysis for two approximation algorithms recently proposed by Calinescu et al. (TCS'02), decreasing the best known approximation factor to 5/3 + /spl epsi/; and a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.

Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RING) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. (1999) recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance /spl par/uv/spl par/ is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2 5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG.

Several localized routing protocols (see Bose, P. and Morin, P., Proc. 10th Annual Int. Symp. on Algorithms and Computation ISAAC, 1999) guarantee the delivery of packets when the underlying network topology is the Delaunay triangulation of all wireless nodes. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we more accurately model the network as a unit-disk graph, UDG, in which a link between two nodes exists only if the distance between them is at most the maximum transmission range. Given a graph H, a spanning subgraph G of H is a t-spanner if the length of the shortest path connecting any two points in G is no more than t times the length of the shortest path connecting the two points in H. We present a novel localized networking protocol that constructs a planar 2.5-spanner of UDG, called the localized Delaunay triangulation, as network topology. It contains all edges that are in both the UDG and the Delaunay triangulation of all wireless nodes. Our experiments show that the delivery rates of existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. The total communication cost of our networking protocol is O(n log n) bits. Moreover, the computation cost of each node u is O(d/sub u/ log d/sub u/), where d/sub u/ is the number of 1-hop neighbors of u in UDG.

Automatic ring protection provides simple and rapid fault protection and restoration in telecommunication networks. To implement the automatic ring protection in general wavelength-division multiplexing (WDM) optical networks, the lightpaths are partitioned into groups each of which can be carried in a simple cycle of the underlying network. As the electronic line terminals are the dominant cost factor in the deployment of WDM optical networks, we study how to generate these partitions with minimum electronic line terminals. This optimization problem is NP-hard. We develop two polynomial-time approximation algorithms, with performance guarantees between 1.5 and 1.6 and between 1.5 and 1.5 + /spl epsi/, respectively. The second algorithm can be adapted, with the same performance guarantees, to the problem in which lightpaths are not prespecified and only the endpoints of each connection are given. Both algorithms can be easily adapted, with the same performance guarantees, to the problem in which only link protection is desired, and each group must be carried in a closed trail. The first algorithm matches and the second algorithm improves the approximation ratio obtained independently by Eilam et al. (see 14th Int. Symp. Distributed Computing, 2000).

Energy conservation is a critical issue in ad hoc wireless networks for node and network life, as the nodes are powered by batteries only. One major approach for energy conservation is to route a communication session along the routes which requires the lowest total energy consumption. This optimization problem is referred to as minimum-energy routing. While minimum-energy unicast routing can be solved in polynomial time by shortest-path algorithms, it remains open whether minimum-energy broadcast routing can be solved in polynomial time, despite the NP-hardness of its general graph version. Previously three greedy heuristics were proposed in Wieselthier et al. (2000): MST (minimum spanning tree), SPT (shortest-path tree), and BIP (broadcasting incremental power). They have been evaluated through simulations in Wieselthier et al.], but little is known about their analytical performance. The main contribution of this paper is the quantitative characterization of their performances in terms of approximation ratios. By exploring geometric structures of Euclidean MSTs, we have been able to prove that the approximation ratio of MST is between 6 and 12, and the approximation ratio of BIP is between /sup 13///sub 3/ and 12. On the other hand, the approximation ratio of SPT is shown to be at least /sup n///sub 2/, where n is the number of receiving nodes. To our best knowledge, these are the first analytical results for minimum-energy broadcasting.

SONET (Synchronous Optical NETworks) add-drop multiplexers (ADMs) are the dominant cost factor in the WDM(Wavelength Division Multiplexing)/SONET rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Previous works took as input the traffic streams with routings given a priori and developed various heuristics for wavelength assignment to minimize the SONET ADM costs. However, little was known about the performance guarantees of these heuristics. This paper contributes mainly in two aspects. First, in addition to the traffic streams with pre-specified routing, this paper also studies minimizing the ADM requirement by traffic streams without given routings, a problem which is shown to be NP-hard. Several heuristics for integrated routing and wavelength assignment are proposed to minimize the SONET ADM costs. Second, the approximation ratios of those heuristics for wavelength assignment only and those heuristics for integrated routing and wavelength assignment are analyzed. The new Preprocessed Iterative Matching heuristic has the best approximation ratio: at most 3/2.

SONET add-drop multiplexers (ADMs) are the dominant cost factor in the SONET/WDM rings. They can potentially be reduced by optical bypass via optical add-drop multiplexers (OADMs) and traffic grooming. In this paper we study the grooming of arbitrary traffic in WDM bidirectional line-switched rings (BLSRs) so as to minimize the ADM cost. Two versions of the minimum ADM cost problem are addressed. In the first version, each traffic stream has a predetermined routing. In the second version, the routing of each traffic stream is not given in advance; however, each traffic stream is fully duplex with symmetric demands, which must be routed along the same path but in opposite directions. In both versions, we further consider two variants depending on whether a traffic stream is allowed to be split at intermediate nodes. All the four combinations are NP-hard even for any fixed line-speed. General lower bounds on the minimum ADM cost are provided. Our traffic grooming follows a two-phased approach. The problem targeted at in each phase is NP-hard itself, except the second phase when the line speed is two. Various approximation algorithms are proposed in both phases, and their approximation ratios are analyzed.

Given an undirected graph wit.h edge co&s and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest.~iULTIW.~yCUT is the problem of finding a multiway cut of minimum cost..Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and %nnr-lkakis gave a performance guarantee of 2 (1 -$), In this paper, we present a new linear programming rslax-&ion for ~fULTIW&Y CUT and a new approximation dgorithm based on it.The algorithm breaks the threshold of 2 for approximating MULTIWAY CUT, achieving a performance ratio of at.most 1.5 -$.This improves the previous result for every value of k.In particular, for k = 3 we get a ratio ofZ