In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each...
详细信息
In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length L.
An underwater acoustic wireless sensor network (UA-WSN) consists of many resourceconstrained underwater sensor nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way to...
详细信息
An underwater acoustic wireless sensor network (UA-WSN) consists of many resourceconstrained underwater sensor nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way to preserve network connectivity while guaranteeing other network QoS is to deploy some relay nodes (RNs) in the networks. Although RNs' function is more powerful than USNs, but they can lead to more interference and their cost is more expensive. This paper addresses constrained low-interference relay node deployment problem for 3-D UA-WSNs in which the RNs are placed at a subset of candidate locations to ensure connectivity between the USNs such that the number of RNs deployed and the value of total incremental interference are minimized. We first prove that it is NP-hard, then propose a general approximation algorithm framework. Based on the framework, we get two polynomial time O(1)-approximation algorithms.
Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense,...
详细信息
ISBN:
(纸本)9780769548937;9781467346245
Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. An interesting subject that has attracted great effort is how to design network topologies with a minimum network resource usage in terms of cost that provides a relibility guarantee. As problems on this subject, like most other network optimization problems, are well-known NP-hard even in their simplest form, design of effective solutions with a guaranteed approximation ratio from the optimal solution has been a major research focus of great significance for both theory and applications. This survery summarizes major existing techniques and results for solving some central problems in designing survivable networks including the minimal connected subgraph problem, the survivable network design problem and the Steiner minimal network problem.
This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e. g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on s...
详细信息
ISBN:
(纸本)9781467307758
This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e. g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.
In this paper, we consider the problem of partitioning a given collection of subsets of nodes into.. collections such that the average size of each collection is the largest, where the size of a collection is defined ...
详细信息
ISBN:
(纸本)9780769548937;9781467346245
In this paper, we consider the problem of partitioning a given collection of subsets of nodes into.. collections such that the average size of each collection is the largest, where the size of a collection is defined as the size of the union of the subsets contained in the collection. At first, we give an upper bound on the performance ratio of Abrams et al.'s approximation algorithm which is known to have a performance ratio of at least 1 - 1/e where e is Napier's constant. The result of numerical calculations indicates that an upper bound is 3/4 + epsilon for small epsilon > 0. Next, we design a distributed implementation of Abrams et al.'s algorithm, which is based on the idea of arbitration using a spanning tree. Our algorithm can be used for the periodical switching of active subsets in Wireless Sensor Networks.
Segmentation of the hand from an image is a necessary step for many applications e.g. hand tracking, gesture recognition. One of the major problems is the hand-forearm segmentation. We propose mathematic model based o...
详细信息
ISBN:
(纸本)9781467318556;9781467318570
Segmentation of the hand from an image is a necessary step for many applications e.g. hand tracking, gesture recognition. One of the major problems is the hand-forearm segmentation. We propose mathematic model based on geometrical features of silhouette shape to address this problem. Then an accurate and effective approximation algorithm is proposed to obtain the solution of the model. Finally a complete hand segmentation algorithm is realized by using the Kinect sensor. The experiment result proves that our algorithm is accurate and fast.
We consider the problem of energy aware scheduling of a set of jobs on a set of unrelated parallel machines with the average weighted completion time plus energy objective. The processing time and the energy consumpti...
详细信息
ISBN:
(纸本)9780769548654;9781467351461
We consider the problem of energy aware scheduling of a set of jobs on a set of unrelated parallel machines with the average weighted completion time plus energy objective. The processing time and the energy consumption of the jobs are machine and speed dependent. Also, every job is subject to a machine-dependent release date. Firstly, we aim to find a non-preemptive schedule of the jobs minimizing the average weighted completion time plus energy, and we propose a randomized approximation algorithm that we derandomize obtaining a deterministic approximation algorithm. We then consider the budget variant of the problem where the objective is to minimize the average completion time while the total energy consumption does not exceed a given budget.
One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surfac...
详细信息
One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP) problem for 3-D underwater acoustic sensor networks. Given a set of underwater sensor nodes (USNs) which are floated at different depths to perform collaborative monitoring tasks over a given region, and a set of candidate locations where SGs may be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or k-connected) from any USN to the base station. We first propose a general algorithm for the connected C-SGP problem and prove its approximation ratio. We also give a constant ratio approximation algorithm for the problem. Second, for the survivable C-SGP problem we also propose a general algorithm and prove its approximation ratio. Finally, we give a constant ratio approximation algorithm for the 2-connected C-SGP problem. (c) 2011 Elsevier B.V. All rights reserved.
The minimum latency data aggregation schedule is one of the fundamental problems in wireless sensor networks. Most existing works assumed that the transmission ranges of sensor nodes cannot be adjusted. However, senso...
详细信息
The minimum latency data aggregation schedule is one of the fundamental problems in wireless sensor networks. Most existing works assumed that the transmission ranges of sensor nodes cannot be adjusted. However, sensors with adjustable transmission ranges have advantages in energy saving, reducing transmission interference and latency. In this paper, we study the minimum latency conflict-aware data aggregation scheduling problem with adjustable transmission radii: given locations of sensors along with a base station, all sensors could adjust their transmission radii and each sensor's interference radius is a times of its transmission radius, we try to find a data aggregation schedule in which the data from all sensors can be transmitted to the base station without conflicts, such that the latency is minimized. We first partition the set of all nodes into two parts: the major set and the minor set. Then, we design different scheduling strategies for the two sets, respectively. Finally, we propose an approximation algorithm for the problem and prove the performance ratio of the algorithm is bounded by a nearly constant. Our experimental results evaluate the efficiency of the proposed algorithm.
暂无评论