We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
@cite_5 studied the min-power routing problem and for uniform demands, i.e. for the case where all the demands have the same value, they proposed a @math -approximation algorithm, where @math , with @math . For non-uniform demands, they proposed a @math -approximation algorithm, where @math is the maximum value of the demands.
@cite_5
2149933233 2950288120 1529079830 1499623512
This paper considers max-min fair rate allocation and routing in energy harvesting networks where fairness is required among both the nodes and the time slots. Unlike most previous work on fairness, we focus on multihop topologies and consider different routing methods. We assume a predictable energy profile and focus on the design of efficient and optimal algorithms that can serve as benchmarks for distributed and approximate algorithms. We first develop an algorithm that obtains a max-min fair rate assignment for any given (time-variable or time-invariable) unsplittable routing or a routing tree. For time-invariable unsplittable routing, we also develop an algorithm that finds routes that maximize the minimum rate assigned to any node in any slot. For fractional routing, we study the joint routing and rate assignment problem. We develop an algorithm for the time-invariable case with constant rates. We show that the time-variable case is at least as hard as the 2-commodity feasible flow problem and design an FPTAS to combat the high running time. Finally, we show that finding a max-min fair unsplittable routing or a routing tree is NP-hard, even for a time horizon of a single slot. Our analysis provides insights into the problem structure and can be applied to other related fairness problems. We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment. This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint We propose a 1.35078-approximation algorithm for the problem (exactly, (√41 - 1) 4), which is an improvement over the existing 1.5-approximation. Reducing power consumption and increasing battery life of nodes in an ad-hoc network requires an integrated power control and routing strategy. Power optimal routing selects the multi-hop links that require the minimum total power cost for data transmission under a constraint on the link quality. This paper studies optimal power routing under the constraint of a fixed end-to-end probability of error and compares the power optimal routes obtained with this criterion with those from the more commonly used fixed per hop error rate constraint. The comparison is carried out by looking at the properties of the power optimal graph, formed by the union of all the power optimal routes. The paper also provides algorithms to determine the power optimal routes.