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

Minimum energy multicast/broadcast routing with reception cost in wireless sensor networks

THEORETICAL COMPUTER SCIENCE 2013年 497卷 173-180页

作者： Li, Deying Liu, Zewen Hong, Yi Chen, Wenping Ma, Huan Renmin Univ China MOE Key Lab Data Engn & Knowledge Engn Beijing Peoples R China Renmin Univ China Sch Informat Beijing 100872 Peoples R China Nanchang Univ Nanchang 330031 Peoples R China

In this paper, we study the minimum energy multicast/broadcast problem with reception cost in wireless sensor networks. Suppose there are n sensors in the network. Each node v has l(v) transmission power levels to choose and its reception cost is B(v) if it receives a message. The problem of our concern is: given a multicast (broadcast) request, how to find a multicast (broadcast) tree such that the total energy cost of the multicast tree including transmitting cost and reception cost is minimized. There are two cases for reception cost: one is that for any node v, the reception cost of v only relies on v itself and is irrelevant with its transmitting node, the other is that the reception cost of v relies on not only itself but also its transmitting node. For the first case, we firstly propose a general approximation algorithm MEB-R-G for the broadcast problem. Moreover, for the multicast problem, we propose a general algorithm MEM-R-G and prove its approximation ratio, we also present a greedy algorithm. For the second case, we also propose a general approximation algorithm MEM-RT-G, and prove its approximation ratio. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Energy efficient Multicast routing Broadcast routing Reception cost approximation algorithm Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

On the Min-Max 2-Cluster Editing Problem

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2013年第6期29卷 1109-1120页

作者： Chen, Li-Hsuan Chang, Maw-Shang Wang, Chun-Chieh Wu, Bang Ye Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan Hungkung Univ Dept Comp Sci & Informat Engn Taichung 433 Taiwan

In this paper, we study the problem Min-Max 2-Cluster Editing which asks for a modification of a given graph into two maximal cliques by inserting or deleting edges such that the maximum number k of the editing edges incident to any vertex is minimized. We show the NP-hardness of the problem and present a polynomial-time algorithm when k < n/4, in which n is number of vertices. In addition, we design a 2-approximation algorithm and a branching algorithm for finding an optimal solution. By experiments on random graphs, we show that the exact algorithm is much more efficient than a trivial one.

关键词： algorithm clustering editing graph modification problem NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the approximability and exact algorithms for vector domination and related problems in graphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第6期161卷 750-767页

作者： Cicalese, Ferdinando Milanic, Martin Vaccaro, Ugo Univ Salerno Dipartimento Informat I-84084 Fisciano SA Italy Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of c In n, where c is a suitable constant and n is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors In Delta + 0(1), where Delta is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Vector domination Total vector domination alpha-domination k-domination Multiple domination Inapproximability approximation algorithm Polynomial time algorithm Trees Threshold graphs P-4-free graphs

来源：评论

学校读者我要写书评

暂无评论

Computing Unrestricted Synopses Under Maximum Error Bound

引用

algorithmICA 2013年第1期65卷 1-42页

作者： Pang, Chaoyi Zhang, Qing Zhou, Xiaofang Hansen, David Wang, Sen Maeder, Anthony CSIRO Australian E Hlth Res Ctr ICT Ctr Brisbane Qld Australia Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia Univ Western Sydney Sch Comp & Math Sydney NSW Australia

Constructing Haar wavelet synopses with guaranteed maximum error on data approximations has many real world applications. In this paper, we take a novel approach towards constructing unrestricted Haar wavelet synopses under maximum error metrics (L (a)). We first provide two linear time (logN)-approximation algorithms which have space complexities of O(logN) and O(N) respectively. These two algorithms have the advantage of being both simple in structure and naturally adaptable for stream data processing. Unlike traditional approaches for synopses construction that rely heavily on examining wavelet coefficients and their summations, the proposed methods are very compact and scalable, and sympathetic for online data processing. We then demonstrate that this technique can be extended to other findings such as Haar(+) tree. Extensive experiments indicate that these techniques are highly practical. The proposed algorithms achieve a very attractive tradeoff between efficiency and effectiveness, surpassing contemporary (logN)-approximation algorithms in compressing qualities.

关键词： approximation algorithm Approximate query processing Data compression Data synopses Haar wavelets

来源：评论

学校读者我要写书评

暂无评论

Optimal approximability of bookmark assignments

引用

DISCRETE APPLIED MATHEMATICS 2013年第16-17期161卷 2361-2366页

作者： Asahiro, Yuichi Miyano, Eiji Murata, Toshihide Ono, Hirotaka Kyushu Sangyo Univ Dept Informat Sci Fukuoka 8138503 Japan Kyushu Inst Technol Dept Syst Design & Informat Fukuoka 8208502 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan

Consider a rooted directed acyclic graph G = (V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper shows the tight bound on the (in)approximability under the assumption P not equal N P: we present a polynomial time approximation algorithm with factor (1 - 1/e), and show that there exists no polynomial time approximation algorithm with a better constant factor than (1 - 1/e) unless P = N P. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Bookmark assignment approximation algorithm Inapproximability

来源：评论

学校读者我要写书评

暂无评论

On bounding node-to-sink latency in wireless sensor networks with multiple sinks

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2013年第1期13卷 13-29页

作者： Kim, Donghyun Wang, Wei Wu, Weili Li, Deying Ma, Changcun Sohaee, Nassim Lee, Wonjun Wang, Yuexuan Du, Ding-Zhu N Carolina Cent Univ Dept Math & Comp Sci Durham NC 27707 USA Xi An Jiao Tong Univ Dept Math Xian 710049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Renmin Univ China Sch Informat Beijing 100872 Peoples R China Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China Univ N Texas Dallas Div Liberal Arts & Life Sci Dallas TX 75241 USA Korea Univ Dept Comp Sci & Engn Seoul 136713 South Korea Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China Korea Univ WCU FNOT Res Ctr Seoul 136713 South Korea

Bounding node-to-sink latency is an important issue of wireless sensor networks (WSNs) with a quality of service requirement. This paper proposes to deploy multiple sinks to control the worst case node-to-sink data latency in WSNs. The end-to-end latency in multihop wireless networks is known to be proportional to the hop length of the routing path that the message moves over. Therefore, we formulate the question of what is the minimum number of sinks and their locations to bound the latency as the minimum d-hop sink placement problem. We also consider its capacitated version. We show problems are NP-hard in unit disk graph (UDG) and unit ball graph, and propose constant factor approximations of the problems in both graph models. We further extend our algorithms so that they can work well in more realistic quasi UDG model. A simulation study is also conducted to see the average performance of our algorithms.

关键词： WSNs wireless sensor networks multiple sink placement relay node placement mobile computing approximation algorithm graph theory UDG unit disk graph UBG unit ball graph quasi unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Coding-Aware Proportional-Fair Scheduling in OFDMA Relay Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2013年第9期24卷 1727-1740页

作者： Tang, Bin Ye, Baoliu Lu, Sanglu Guo, Song Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210046 Jiangsu Peoples R China Univ Aizu Sch Comp Sci & Engn Performance Evaluat Lab Aizu Wakamatsu Fukushima 9658580 Japan

In recent years, OFDMA relay networks have become a key component in the 4G standards (e. g., IEEE 802.16j, 3GPP LTE-Advanced) for broadband wireless access. When numerous bidirectional flows pass through the relay stations in an OFDMA relay network that supports various interactive applications, plenty of network coding opportunities arise and can be leveraged to enhance the throughput. In this paper, we study the proportional-fair scheduling problem in the presence of network coding in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two models, global approach (GA) and local approach (LA), under which the corresponding problems are shown both NP-hard. For the GA model, we show that it cannot be approximated within some constant factor. Hence, we propose a heuristic algorithm with low time complexity. For the LA model, we propose a theoretical polynomial time approximation scheme (PTAS), and also present a practical greedy algorithm with approximation factor of 1/2. Simulation results show that our algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.

关键词： Network coding OFDMA relay networks proportional-fair scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

CONVEX RELAXATIONS OF THE WEIGHTED MAXMIN DISPERSION PROBLEM

引用

SIAM JOURNAL ON OPTIMIZATION 2013年第4期23卷 2264-2294页

作者： Haines, Sheena Loeppky, Jason Tseng, Paul Wang, Xianfu UBC Okanagan Irving K Barber Sch Kelowna BC V1V 1V7 Canada Univ Washington Dept Math Seattle WA 98195 USA

Consider the weighted maxmin dispersion problem of locating point(s) in a given region chi subset of R-n that is/are furthest from a given set of m points. The region is assumed to be convex under componentwise squaring. We show that this problem is NP-hard even when chi is a box and the weights are equal. We then propose a convex relaxation of this problem for finding an approximate solution and derive an approximation bound of 1-O(root ln(m)gamma*)/2, where gamma* depends on chi. When chi is a box or a product of low-dimensional spheres, gamma* = O(1/n) and the convex relaxation reduces to a semidefinite program and a second-order cone program.

关键词： maxmin dispersion semidefinite programming relaxation second-order cone programming relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximations for the Two-Machine Cross-Docking Flow Shop Problem

引用

DISCRETE APPLIED MATHEMATICS 2013年第13-14期161卷 2107-2119页

作者： Prot, D. Rapine, C. G SCOP Concept Optimizat & Prod Lab F-38031 Grenoble France LUNAM Univ Ecole Mines Nantes IRCCyN UMR CNRS 6597 Inst Rech Commun & Cybernet Nantes F-44307 Nantes 3 France

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree. (C) 2013 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Typed tasks Precedence constraints Makespan

来源：评论

学校读者我要写书评

暂无评论

Minimum Broadcasting Structure for Optimal Data Dissemination in Vehicular Networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2013年第8期62卷 3964-3973页

作者： Ros, Francisco J. Ruiz, Pedro M. Univ Murcia Dept Informat & Commun Engn E-30001 Murcia Spain

In this paper, we model a vehicular multihop network as an evolving graph and formulate the problem of optimal data dissemination over the network in terms of minimum number of transmissions. We show that the problem belongs to the NP complexity class and provide an easy to implement polynomial-time 2 tau H(Delta)-approximation algorithm, where tau is the number of different subgraphs that comprise the evolving graph, and H(Delta) is the harmonic number of the degree of the evolving graph. By means of applying our heuristic over a vehicular scenario generated by a microscopic road-traffic simulator, we provide some insight into the data dissemination issue. In addition, the proposed algorithm is employed to benchmark a state-of-the-art communication protocol. We hope this paper will inspire more efficient heuristics and data dissemination solutions.

关键词： approximation algorithm broadcasting data dissemination evolving graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：