Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a m...
详细信息
Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged;another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.
Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is pr...
详细信息
Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is predicted from its amino acid sequence. The secondary structure refers to the local sub-structures of a protein. Simplified energy models have been proposed in the literature on the basis of interaction of amino acid residues in proteins. We focus on a well researched model known as the Hydrophobic-Polar (HP) energy model. In this paper, we propose the hexagonal prism lattice with diagonals that can overcome the problems of other lattice structures, e.g., parity problem. We give two approximation algorithms for protein folding on this lattice using HP model. Our first algorithm leads us to a similar structure of helix structure that is commonly found in a protein structure. This motivates us to propose the next algorithm with a better approximation ratio. Finally, we analyze the algorithms on the basis of intensity of the chemical forces along the different types of edges of hexagonal prism lattice with diagonals.
Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize mak...
详细信息
Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize makespan. A soaking furnace can be seen as a parallel batch processing machine. In order to avoid the thermal stress caused by excessive temperature difference, initial temperature is needed for the ingot before processing. With the increasing of waiting time, the ingot temperature decreases and the soaking time increases. This property is called deterioration. Setup time is needed between incompatible jobs. We show that if jobs have the same sizes, an optimal solution can be found within O(nlogn) time. If jobs have identical processing times, the problem is proved to be NP-hard in the strong sense. We propose an approximate algorithm whose absolute and asymptotic worst-case ratios are less than 2 and 11/9, respectively. When the jobs have arbitrary sizes and arbitrary processing times, the model is also NP-hard in the strong sense. An approximate algorithm with an absolute and asymptotic worst-case ratio less than 2 is proposed. The time complexity is O(nlogn).
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v is an element of V to S is at most a given bound d and the average distance fro...
详细信息
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v is an element of V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.
We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground pla...
详细信息
We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground plane. The common angle alpha of the cones represent the field of view of the onboard camera. The cone heights, which can be varying, correspond with the desired observation quality (e.g. resolution). This problem is a novel variant of the traveling salesman problem with neighborhoods (TSPN). We name it Cone-TSPN. Our main contribution is a polynomial time approximation algorithm for Cone-TPSN. We analyze its theoretical performance and show that it returns a solution whose length is at most O(1+log(hmax/hmin)) times the length of the optimal solution where hmax and hmin are the heights of the tallest and shortest input cones, *** demonstrate the use of our algorithm in a representative precision agriculture application. Wefurther study its performance in simulation using randomly generated cone sets. Our results indicate that the performance of our algorithm is superior to standard solutions.
We consider a problem of locating communication centers. In this problem, it is required to partition the set of n customers into subsets minimizing the length of nets required to connect all the customers to the comm...
详细信息
We consider a problem of locating communication centers. In this problem, it is required to partition the set of n customers into subsets minimizing the length of nets required to connect all the customers to the communication centers. Suppose that communication centers are to be placed in p of the customers locations. The number of customers each center supports is also given. The problem remains to divide a graph into sets of the given sizes, keeping the sum of the spanning trees minimal. The problem is NP-complete, and no polynomial algorithm with bounded error ratio can be given, unless P=NP. We present an approximation algorithm for the problem assuming that the edge lengths satisfy the triangle inequality. It runs in O(p(2)4(p) + n(2)) time (n = \V\) and comes within a factor of 2p - 1 of optimal. When the sets' sizes are all equal this algorithm runs in O(n2) time. Next, an improved algorithm is presented which obtains as an input a positive integer x (x less than or equal to n - p) and runs in O(f(p,x)n(2)) time, where f is an exponential function of p and x, and comes within a factor of 2 + (2p - 3)/x of optimal. When the sets' sizes are all equal it runs in O(2((p+x))n(2)) time. A special algorithm is presented for the case p = 2. (C) 1998 Elsevier Science B.V. All rights reserved.
We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications...
详细信息
We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a MINIMUM SET COVER instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of 0(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions. (C) 2002 Published by Elsevier Science B.V.
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623-644, 1977;Jaitly et al. in J. Comput. Syst. Sci. 65:494-507, 2002;Tang et al. in...
详细信息
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623-644, 1977;Jaitly et al. in J. Comput. Syst. Sci. 65:494-507, 2002;Tang et al. in J. Comput. Biol. 9:429-446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n (5)) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002) takes O(n (11)) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.
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 minimnm-load klacility location (MLkF...
详细信息
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 minimnm-load klacility 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 subset of F of k facilities and assign each client j to a-facility f (j) is an element of F so as to minimize max(f is an element of F) Sigma(j is an element of C:f(j)=f) d(f, j);we call Sigma(j is an element of 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 MLkFL for when F = C. MLkFL is rather poorly understood, a rid only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polytime 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 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 MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near optimal solution possessing sonic 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
The emerging wireless relay networks (WRNs) are expected to provide significant improvement on throughput and extension of coverage area for next-generation wireless systems. We study an optimization problem for multi...
详细信息
The emerging wireless relay networks (WRNs) are expected to provide significant improvement on throughput and extension of coverage area for next-generation wireless systems. We study an optimization problem for multihop link scheduling with bandwidth and delay guarantees over WRNs. Our optimization problem is investigated under a more general interference model with a generic objective. The objective can be based on various kinds of performance indexes (e.g., throughput, fairness, and capacity), which can be determined by service providers. Through our theoretical analysis, the intractability and inapproximability of the optimization problem are shown. Due to the intractable computational complexity, we present efficient algorithms to provide a reasonable small approximation factor against any optimal solution even for a worst-case input. Furthermore, some experimental results indicate that our algorithms yield near-optimal performance in the average case.
暂无评论