检索结果-内蒙古大学图书馆

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Huc, Florian Jarry, Aubin Leone, Pierre Rolim, Jose Univ Geneva Dept Comp Sci CH-1211 Geneva 4 Switzerland

ISBN: (纸本)9781605588889

We study the problem of routing messages in sensor networks where the energy saving issue is essential. In this paper, we propose ROAM2, an improvement of ROAM (Routing protocol with Obstacle Avoidance Mechanism) proposed in [HJL(+)09]. This distributed protocol has a light obstacle detection and avoidance component with low message and computation overhead and a routing component which sends messages along short paths, thus saving energy. We improved it so that is has an 100% delivery rate and we prove that ROAM finds with high probability paths whose lengths are comparable to the length of the shortest paths. Furthermore, we prove a general result on the length of any path computed in a greedy way. Whereas ROAM uses one bit of memory in nodes (even if there are several destinations), in [KWZ08], it was shown that no geographic routing algorithm not using any sensor memory can compute a path whose length is guaranteed to be of order less than O(l(2)), where l is the length of the shortest path. Finally, we compare the energy efficiency of ROAM against GPSR (or GFG) [KK00], the algorithm proposed in [MLNR08] and SLGF [JMLW08], by running simulations which validates our theoretical results.

关键词： approximation algorithm Obstacle Avoidance Routing Sensor Network

来源：评论

学校读者我要写书评

暂无评论

PreDVS: Preemptive Dynamic Voltage Scaling for Real-time Systems using approximation Scheme 10

PreDVS: Preemptive Dynamic Voltage Scaling for Real-time Sys...

引用

47th Design Automation Conference (DAC)

作者： Wang, Weixun Mishra, Prabhat Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

ISBN: (纸本)9781450300025

System optimization techniques based on dynamic voltage scaling (DVS) are widely used with the aim of reducing processor energy consumption. Inter-task DVS assigns the same voltage level to all the instances of each task. Its intra-task counterpart exploits more energy savings by assigning multiple voltage levels within each task. In this paper, we propose a voltage scaling technique, named PreDVS, which assigns voltage levels based on the task set's preemptive scheduling for hard real-time systems. Our approach is based on an approximation scheme hence can guarantee to generate solutions within a specified quality bound (e.g., within 1% of the optimal) and is different from any existing inter-or intratask DVS techniques. PreDVS exploits static time slack at a finer granularity and achieves more energy saving than inter-task scaling without introducing any extra voltage switching overhead. Moreover, it can be efficiently employed together with existing intra-task scaling techniques. Experimental results demonstrate that PreDVS can significantly reduce energy consumption and outperform the optimal inter-task voltage scaling techniques by up to 24%.

关键词： Real-time systems energy-aware scheduling dynamic voltage scaling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Sorting Unsigned Permutations by Weighted Reversals,Transpositions,and Transreversals

引用

Journal of Computer Science & Technology 2010年第4期25卷 853-863页

作者：娄晓文朱大铭 School of Computer Science and Technology Shandong University

Reversals, transpositions and transreversals are common events in genome rearrangement. The genome rearrangement sorting problem is to transform one genome into another using the minimum number of given rearrangement operations. An integer permutation is used to represent a genome in many cases. It can be divided into disjoint strips with each strip denoting a block of consecutive integers. A singleton is a strip of one integer. And the genome rearrange- ment problem turns into the problem of sorting a permutation into the identity permutation equivalently. Hannenhalli and Pevzner designed a polynomial time algorithm for the unsigned reversal sorting problem on those permutations with O（logn） singletons. In this paper, first we describe one case in which Hannenhalli and Pevzner＇s algorithm may fail and propose a corrected approach. In addition, we propose a （1 ＋ ε）-approximation algorithm for sorting unsigned permutations with O（log n） singletons by reversals of weight 1 and transpositions/transreversals of weight 2.

关键词： approximation algorithm genome rearrangement sorting reversal transposition

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

引用

MATHEMATICS OF OPERATIONS RESEARCH 2010年第4期35卷 795-806页

作者： Lee, Jon Sviridenko, Maxim Vondrak, Jan IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA IBM Almaden Res Ctr San Jose CA 95120 USA

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs;certain constraint satisfaction problems;maximum entropy sampling;and maximum facility location problems. Our main result is that for any k >= 2 and any epsilon > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves upon the 1/(k+1)-approximation of Fisher, Nemhauser, and Wolsey obtained in 1978 [Fisher, M., G. Nemhauser, L. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions-II. Math. Programming Stud. 8 73-87]. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general nonmonotone submodular function subject to k matroid constraints. We show that, in these cases, the approximation guarantees of our algorithms are 1/(k-1+epsilon) and 1/(k+1+1/(k-1)+epsilon), respectively. Our analyses are based on two new exchange properties for matroids. One is a generalization of the classical Rota exchange property for matroid bases, and another is an exchange property for two matroids based on the structure of matroid intersection.

关键词： matroid submodular function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Coverage and connected coverage problems for sensors embedded in a temperature-sensitive environment

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2010年第1-2期7卷 106-123页

作者： Sen, Arunabha Das, Nibedita Murthy, Sudheendra Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85281 USA

Several issues are encountered during deployment of bio-sensors in a human or animal body. Radio transmitters during operation dissipate energy and raise the temperature of its surroundings. A temperature-sensitive environment, such as the human body, can tolerate such increase in temperature only up to a certain threshold value, beyond which serious injury may result. To avoid such injury, the sensor placement must be carried out in a way that ensures the surrounding area temperature remains within the threshold. Using a thermal model for heat distribution from multiple heat sources (radio transmitters), we observed that if the sensor nodes are placed sufficiently apart from each other, then the temperature of the surrounding area does not exceed the threshold. This minimum separation distance constraint gives rise to a new variation of the sensor coverage problem.

关键词： sensor coverage connectivity body sensor network NP-completeness single-hop network multi-hop network approximation algorithm generalised set cover problem generalised independent set problem

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING WITH DISCRETELY COMPRESSIBLE RELEASE DATES TO MINIMIZE MAKESPAN

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2010年第4期27卷 493-501页

作者： Zhang, Shu-Xia Cao, Zhi-Gang Zhang, Yu-Zhong Zhenjiang Watercraft Coll Dept Watercraft Command Zhenjiang 212003 Jiangsu Peoples R China Chinese Acad Sci AMSS Key Lab Management Decis & Informat Syst Beijing 100190 Peoples R China Qufu Normal Univ Coll Operat Res & Management Sci Sch Operat Res & Management Sci Rizhao 276826 Shandong Peoples R China

In this paper, we address the scheduling model with discretely compressible release dates, where processing any job with a compressed release date incurs a corresponding compression cost. We consider the following problem for the first time: scheduling with discretely compressible release dates to minimize the sum of makespan plus total compression cost. We show its NP-hardness, and design an approximation algorithm with worst-case performance ratio 2, which is the best possible if the processing order of the jobs is pre-specified.

关键词： Scheduling discretely compressible release dates approximation algorithm makespan

来源：评论

学校读者我要写书评

暂无评论

Complexity results for Weighted Timed Event Graphs

引用

DISCRETE OPTIMIZATION 2010年第3期7卷 166-180页

作者： Marchetti, Olivier Munier-Kordon, Alix Univ Paris 06 Lab LIP6 F-75252 Paris 05 France

The minimization of the amount of initial tokens in a Weighted Timed Event Graph (in short WTEG) or a Timed Event Graph (in short TEG) under throughput constraint is a crucial problem in industrial area such as the design of manufacturing systems or embedded systems. Two important variants are studied in this paper: the first one concerns the maximization of the throughput for minimum places capacities of a TEG. It is proved NP-complete by a polynomial reduction with the K-colorability problem. The second one is the minimization of the overall places capacities with a maximum throughput. This problem is also proved NP-complete for a TEG. A polynomial subcase and a 2-approximation polynomial algorithm for a WTEG are then provided. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Weighted Timed Event Graphs Throughput Buffer requirement Complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximations for node-weighted Steiner tree in unit disk graphs

引用

OPTIMIZATION LETTERS 2010年第3期4卷 405-416页

作者： Xu, X. Wang, Y. Du, H. Wan, P. -J. Zou, F. Li, X. Wu, W. IIT Dept Comp Sci Chicago IL 60616 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Lanzhou Univ Sch Math & Stat Lanzhou 730000 Peoples R China

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278-285) showed that any mu-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 mu-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy algorithm whose approximation bound converges to 1 + ln 5 approximate to 2. 61 as k --> infinity, the 3-Restricted Greedy algorithm with approximation bound 4 1/3, and the k-Restricted Variable Metric algorithm whose approximation bound converges to 3.9334 as k --> infinity.

关键词： Node-weighted Steiner tree Unit-disk graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Metric Clustering to Minimize the Sum of Radii

引用

algorithmICA 2010年第3期57卷 484-498页

作者： Gibson, Matt Kanade, Gaurav Krohn, Erik Pirwani, Imran A. Varadarajan, Kasturi Univ Iowa Dept Comp Sci Iowa City IA 52242 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

Given an n-point metric (P,d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n (O(log na <...log Delta)) time and returns with high probability the optimal solution. Here, Delta is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.

关键词： Clustering Polynomial time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing the sum of weighted completion times in a concurrent open shop

引用

OPERATIONS RESEARCH LETTERS 2010年第5期38卷 390-395页

作者： Mastrolilli, Monaldo Queyranne, Maurice Schulz, Andreas S. Svensson, Ola Uhan, Nelson A. Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Univ British Columbia Sauder Sch Business Vancouver BC V5Z 1M9 Canada IDSIA Manno Switzerland MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA MIT Ctr Operat Res Cambridge MA 02139 USA KTH Comp Sci & Commun Stockholm Sweden

We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if not equal NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling Integrality gap approximation algorithm Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：