An Underwater Acoustic Wireless Sensor Network (UA-WSN) consists of many resource-constrained Underwater Sensor Nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way t...
详细信息
ISBN:
(纸本)9783642174605
An Underwater Acoustic Wireless Sensor Network (UA-WSN) consists of many resource-constrained Underwater Sensor Nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way to preserve network connectivity while guaranteing other network QoS is to deploy some Relay Nodes (RNs) in the networks, in which RNs' function is more powerful than USNs and their cost is more expensive. This paper addresses Constrained Low-interference Relay Node Deployment (C-LRND) problem for 3-D UA-WSNs in which the RNs are placed at a subset of candidate locations to ensure connectivity between the USNs, under both the number of RNs deployed and the value of total incremental interference constraints. We first prove that it is NP-hard, then present a general approximation algorithm framework and get two polynomial time O(1)-approximation algorithms.
A new n log n algorithm for the scheduling problem of n independent jobs on m identical parallel machines with minimum makespan objective is proposed and its worst-case performance ratio is estimated. The algorithm it...
详细信息
We consider the clustering with diversity problem: given a set of colored points in a metric space, partition them into clusters such that each cluster has at least e points, all of which have distinct colors. We give...
详细信息
ISBN:
(数字)9783642141652
ISBN:
(纸本)9783642141645
We consider the clustering with diversity problem: given a set of colored points in a metric space, partition them into clusters such that each cluster has at least e points, all of which have distinct colors. We give a 2-approximation to this problem for any when the objective is to minimize the maximum radius of any cluster. We show that the approximation ratio is optimal unless P = NP, by providing a matching lower bound. Several extensions to our algorithm have also been developed for handling outliers. This problem is mainly motivated by applications in privacy-preserving data publication.
In many signal processing and data mining applications, we need to approximate a given matrix Y with a low-rank product Ya parts per thousand AX. Both matrices A and X are to be determined, but we assume that from the...
详细信息
In many signal processing and data mining applications, we need to approximate a given matrix Y with a low-rank product Ya parts per thousand AX. Both matrices A and X are to be determined, but we assume that from the specifics of the application we have an important piece of a-priori knowledge: A must have zeros at certain positions. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is whether the known zero pattern of A contributes to the uniqueness of the factorization. Using the notion of structural rank, we present a combinatorial characterization of uniqueness up to diagonal scaling (subject to a mild non-degeneracy condition on the factors), called structural identifiability of the model. Next, we define an optimization problem that arises in the need for efficient experimental design. In this context, Y contains sensor measurements over several time samples, X contains source signals over time samples and A contains the source-sensor mixing coefficients. Our task is to monitor the signal sources with the cheapest subset of sensors, while maintaining structural identifiability. Firstly, we show that this problem is NP-hard. Secondly, we present a mixed integer linear program for its exact solution together with two practical incremental approaches. We also propose a greedy approximation algorithm. Finally, we perform computational experiments on simulated problem instances of various sizes.
作者：
Nguyen, Viet HungNguyen, Thi Thu ThuyLIP6
Université Pierre et Marie Curie Paris 6 75252 Paris Cedex 05 4 Place Jussieu France Department of Mathematics
Ecole Internationale des Sciences de Traitement de l'Information (EISTI) Cergy Cedex Avenue du Parc 95011 France
We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of pena...
详细信息
We considered the single machine scheduling with fixed delivery dates and temporary storage. The objective is to minimize the sum of the makespan and the total inventory costs. We showed that the problem is strongly N...
详细信息
ISBN:
(纸本)9781424473281
We considered the single machine scheduling with fixed delivery dates and temporary storage. The objective is to minimize the sum of the makespan and the total inventory costs. We showed that the problem is strongly NP-hard and polynomial-time approximation algorithm with a fixed performance ratio does not exist for the problem unless P=NP. A polynomial 3/2-approximation algorithm for the case with period delivery times was presented and the performance ratio of 3/2 can not be improved unless P=NP.
The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is NP-hard and ...
详细信息
ISBN:
(纸本)9783642112652
The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is NP-hard and a recent quasi-PTAS suggests that a PTAS might be in reach. Yet, so far it has resisted any attempt for constant-factor approximation algorithms. We relate the tractability of the problem to structural properties of customers' valuations. We show that the problem becomes NP-hard as soon as the average valuations of customers are not;homogeneous, even under further restrictions such as monotonicity. Moreover, we derive an efficient;approximation algorithm, parameterized along the inhomogeneity of customers' valuations. Finally, we discuss extensions of our results that go beyond the highway pricing problem.
Given an undirected connected graph G we consider the problem of finding a spanning tree of G with a maximum number of internal (≥ 2 degree) vertices. This problem, called the Maximum Internal Spanning Tree problem, ...
详细信息
Unit disk graphs are the intersection graphs of equal sized disks in the plane, they are widely used as a mathematical model for wireless ad-hoc networks and some problems in computational geometry. In this paper we f...
详细信息
Unit disk graphs are the intersection graphs of equal sized disks in the plane, they are widely used as a mathematical model for wireless ad-hoc networks and some problems in computational geometry. In this paper we first show that Roman dominating set and connected Roman dominating set problems in unit disk graphs are NP-complete, and then present two approximation algorithms for these problems.
In recent years Google's Map Reduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo in daily use, and more recently put in us...
详细信息
ISBN:
(纸本)9781450300797
In recent years Google's Map Reduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines Hadoop is a free Java implementation of Map Reduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network Each job is also split into many small pieces called tasks Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers Given a placement of the input data over servers, one wishes to final the assignment that minimizes the completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that. there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.
暂无评论