Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

An approximation algorithm for the wireless gathering problem

The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.     

Bounded-hops power assignment in ad hoc wireless networks

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). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥^κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)^κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥^κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.     

Data volume reduction in covering approximation spaces with respect to twenty-two types of covering based rough sets

In this paper, we investigate whether consistent mappings can be used as homomorphism mappings between a covering based approximation space and its image with respect to twenty-two pairs of covering upper and lower approximation operators. We also consider the problem of constructing such mappings and minimizing them. In addition, we investigate the problem of reducing the data volume using consistent mappings as well as the maximum amount of their compressibility. We also apply our algorithms against several datasets.     

Fully polynomial-time approximation schemes for time–cost tradeoff problems in series–parallel project networks

We consider the deadline problem and budget problem of the nonlinear time–cost tradeoff project scheduling model in a series–parallel activity network. We develop fully polynomial-time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.     

Connectivity guarantees for wireless networks with directional antennas

We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible.We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an α-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,q∈P are connected by an edge in G, if and only if q lies in p?s wedge and p lies in q?s wedge.) We prove that if α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an time algorithm for adjusting the wedges, where k is the size of the convex hull of P.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε.     

Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFL_β[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is c_ij. For iF, the cost of opening a facility at location i is f_i0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem.     

Optimizing bandwidth allocation in elastic optical networks with application to scheduling

We study a problem of optimal bandwidth allocation in the elastic optical networks technology, where usable frequency intervals are of variable width. In this setting, each lightpath has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we seek a bandwidth assignment that maximizes the total profit. This problem is known to be NP-complete. We strengthen this result by showing that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Some of our results resolve open problems posed by Shalom et al. (2013) [28]. Our study has applications also in real-time scheduling.     

An approximation algorithm for a facility location problem with stochastic demands and inventories

We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating costs and inventory costs.     

Capacity planning in networks of queues with manufacturing applications

This paper addresses capacity planning in systems that can be modeled as a network of queues. More specifically, we present an optimization model and solution methods for the minimum cost selection of capacity at each node in the network such that a set of system performance constraints is satisfied. Capacity is controlled through the mean service rate at each node. To illustrate the approach and how queueing theory can be used to measure system performance, we discuss a manufacturing model that includes upper limits on product throughput times and work-in-process in the system. Methods for solving capacity planning problems with continuous and discrete capacity options are discussed. We focus primarily on the discrete case with a concave cost function, allowing fixed charges and costs exhibiting economies of scale with respect to capacity to be handled.     

Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges

Wireless sensor networks involve many different real-world contexts, such as monitoring and control tasks for traffic, surveillance, military and environmental applications, among others. Usually, these applications consider the use of a large number of low-cost sensing devices to monitor the activities occurring in a certain set of target locations. We want to individuate a set of covers (that is, subsets of sensors that can cover the whole set of targets) and appropriate activation times for each of them in order to maximize the total amount of time in which the monitoring activity can be performed (network lifetime), under the constraint given by the limited power of the battery contained in each sensor. A variant of this problem considers that each sensor can be activated in a certain number of alternative power levels, which determine different sensing ranges and power consumptions. We present some heuristic approaches and an exact approach based on the column generation technique. An extensive experimental phase proves the advantage in terms of solution quality of using adjustable sensing ranges with respect to the classical single range scheme.     

Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint

We study the problem of scheduling n non-preemptable jobs on a single machine which is not available for processing during a given time period. The objective is to minimize the sum of the job completion times. The best known approximation algorithm for this NP-hard problem has a relative worst-case error bound of 17.6%. We present a parametric O(nlog n)-algorithm H with which better worst-case error bounds can be obtained. The best error bound calculated for the algorithm in the paper is 7.4%. In a computational experiment, we test the algorithm with the performance guarantee set to 10.2%. It turns out that randomly generated instances with up to 1000 jobs can be solved with a mean (maximum) error of 0.31% (3.18%) and a mean (maximum) computation time of 0.8 (9.7) seconds.     

Tighter approximation bounds for LPT scheduling in two special cases

$Q||C_{\max }$ denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of $Q||C_{\max }$ are considered: case I, when $m?1$ machine speeds are equal, and there is only one faster machine; and case II, when machine speeds are all powers of 2 (2-divisible machines). Case I has been widely studied in the literature, while case II is significant in an approach to design so called monotone algorithms for the scheduling problem.We deal with the worst case approximation ratio of the classic list scheduling algorithm ‘Largest Processing Time (LPT)’. We provide an analysis of this ratio $\mathit{Lpt}/\mathit{Opt}$ for both special cases: For ‘one fast machine’, a tight bound of $(\sqrt{3}+1)/2\approx 1.3660$ is given. For 2-divisible machines, we show that in the worst case $1.3673<\mathit{Lpt}/\mathit{Opt}<1.4$. Besides, we prove another lower bound of $955/699>(\sqrt{3}+1)/2$ when LPT breaks ties arbitrarily.To our knowledge, the best previous lower and upper bounds were $(4/3,3/2?1/2m]$ in case I [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166], respectively $[4/3?1/3m,3/2]$ in case II [R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17 (1969) 416–429; A. Kovács, Fast monotone 3-approximation algorithm for scheduling related machines, in: Proc. 13th Europ. Symp. on Algs. (ESA), in: LNCS, vol. 3669, Springer, 2005, pp. 616–627]. Moreover, Gonzalez et al. conjectured the lower bound 4/3 to be tight in the ‘one fast machine’ case [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166].     

Routing of single-source and multiple-source queries in static sensor networks

In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For single-source-queries routing, we utilise a centralised mechanism to accomplish a query using an asymptotically optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(clogn), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n²D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the positions of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It is also worth mentioning that a lower bound of Ω(c²) transmissions has been proved if preprocessing is not allowed [F. Kuhn, R. Wattenhofer, A. Zollinger, Asymptotically optimal geometric mobile ad-hoc routing, in: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, GA, September 2002, pp. 24–33].     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.