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

Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2011年第6期E94B卷 1630-1639页

作者： Katayama, Nozomu Fujimura, Takeshi Miwa, Hiroyoshi Kamiyama, Noriaki Hasegawa, Haruhisa Yoshino, Hideaki Kwansei Gakuin Univ Sanda 6691337 Japan NTT Corp NTT Serv Integrat Labs Musashino Tokyo 1808585 Japan

When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable as possible, i.e., minimizing the difference in hop length between the original flow and the rerouted flow is important for network reliability. Therefore, network service providers need a method for designing networks that stabilizes the flow hop length and maintains connectivity during a link or node failure with limited investment cost. First, we formulate the network design problem used for determining the set of links to be added that satisfies the required constraints on flow hop length stability, connectivity, and node degree. Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. Evaluation of the performance of these algorithms by using 39 backbone networks of commercial ISPs and networks generated by two well-known models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.

关键词： quality of service backbone network optimization problem NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Accelerating identification of custom instructions for extensible processors

引用

IET CIRCUITS DEVICES & SYSTEMS 2011年第1期5卷 21-32页

作者： Li, T. Jigang, W. Deng, Y. Srikanthan, T. Lu, X. Natl Univ Def Technol Sch Comp Sci & Technol Changsha 410073 Hunan Peoples R China Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore

Extensible processors are increasingly becoming popular as they allow for incorporating custom instructions to meet design constraints. Identifying custom instructions is a time-consuming process particularly when large applications are considered. In this study, efficient techniques for identifying custom instruction candidates are proposed. New pruning criteria are introduced and combined with the latest work cited in the literature to accelerate the identification process. The proposed techniques have been shown to be capable of enumerating all valid patterns corresponding to given micro-architectural constraints with reduced search space. Experimental results show that, the proposed algorithm is capable of reducing the runtime by up to 50% for the case of single-output constraint, and by up to 44% for the case of multiple-output constraint. In addition, an approximation algorithm is also proposed to select the valid pattern that provides for maximum gain in execution of applications. In particular, the proposed algorithm focuses on the promising candidates, instead of enumerating all valid patterns as was the case in previous algorithms. It has been shown to be capable of obtaining the optimal valid pattern for most cases of I/O constraints and the runtime has been reduced by up to 90% for some I/O constraints.

关键词： extensible processors application-specific integrated circuits identification acceleration instruction sets microarchitectural constraints custom instructions approximation algorithm multiple-output constraint pruning criteria search space design constraints I/O constraints microprocessor chips

来源：评论

学校读者我要写书评

暂无评论

On the Planarization of Wireless Sensor Networks

引用

algorithmICA 2011年第3期60卷 593-608页

作者： Zhang, Fenghui Jiang, Anxiao (Andrew) Chen, Jianer Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

Network planarization has been an important technique in numerous sensornet protocols-such as Greedy Perimeter Stateless Routing (GPSR), topology discovery, data-centric storage, etc.-however the planarization process itself has been difficult. Known efficient planarization algorithms exist only for restrictive wireless network models: unit-disk graphs with accurately known location information. In this paper, we study efficient planarization of wireless sensor networks, and present a novel planarization method for a more general network model, where sensors can have non-uniform transmission ranges and no location information is needed. Our planarization algorithms also include a (2+epsilon)-approximation algorithm and an FPT algorithm for the bipartite planarization problem.

关键词： Sensor network Network planarization Graph drawing Bipartite planarization approximation algorithm Parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Integration Gain of Heterogeneous WiFi/WiMAX Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2011年第8期10卷 1131-1143页

作者： Wang, Wei Liu, Xin Vicente, John Mohapatra, Prasant Nokia Res Ctr Beijing 100176 Peoples R China Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Intel Corp Folsom CA 95630 USA

We study the integrated WiFi/WiMAX networks, where users are equipped with dual-radio interfaces that can connect to either a WiFi or a WiMAX network. Previous research on integrated heterogeneous networks (e. g., WiFi/cellular) usually considers one network as the main and the other as the auxiliary. The performance of the integrated network is compared with the "main" network. The gain is apparently due to the additional resources from the auxiliary network. In this study, we are interested in integration gain that comes from the better utilization of the resource rather than the increase of the resource. The heterogeneity of the two networks is the fundamental reason for the integration gain. To quantify it, we design a generic framework that supports different performance objectives. We focus on the max-min throughput fairness in this work and also briefly cover the proportional fairness metric. We first prove that it is NP-hard to achieve integral max-min throughput fairness, then propose a heuristic algorithm, which provides two-approximation to the optimal fractional solution. Simulation results demonstrate significant integration gain from three sources, namely, spatial multiplexing, multinetwork diversity, and multiuser diversity. For the proportional fairness metric, we derive the formulation and propose a heuristic algorithm, which shows satisfactory performance when compared with the optimal solution.

关键词： WiFi WiMAX heterogeneous network integration gain NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with semi-resumable machineavailability constraints

引用

Applied Mathematics(A Journal of Chinese Universities) 2011年第2期26卷 177-186页

作者： CHEN Yong ZHANG An TAN Zhi-yi Department of Mathematics Zhejiang University Hangzhou 310027 China

This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also *** the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.

关键词： Scheduling Machine maintenance approximation algorithm Worst-case analysis.

来源：评论

学校读者我要写书评

暂无评论

Sweeping an oval to a vanishing point

引用

DISCRETE APPLIED MATHEMATICS 2011年第14期159卷 1436-1442页

作者： Dumitrescu, Adrian Jiang, Minghui Utah State Univ Dept Comp Sci Logan UT 84322 USA Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA

Given a convex region in the plane, and a sweep-line as a tool, what is the best way to reduce the region to a single point by a sequence of sweeps? The problem of sweeping points by orthogonal sweeps was first studied in [2]. Here we consider the following slanted variant of sweeping recently introduced in [1]: in a single sweep, the sweep-line is placed at a start position somewhere in the plane, then moved continuously according to a sweep vector (upsilon) over right arrow (not necessarily orthogonal to the sweep-line) to another parallel end position, and then lifted from the plane. The cost of a sequence of sweeps is the sum of the lengths of the sweep vectors. The optimal sweeping cost of a region is the infimum of the costs over all finite sweeping sequences for that region. An optimal sweeping sequence for a region is one with a minimum total cost, if it exists. Another parameter of interest is the number of sweeps. We show that there exist convex regions for which the optimal sweeping cost cannot be attained by two sweeps. This disproves a conjecture of Bousany, Karker, O'Rourke, and Sparaco stating that two sweeps (with vectors along the two adjacent sides of a minimum-perimeter enclosing parallelogram) always suffice [1]. Moreover, we conjecture that for some convex regions, no finite sweeping sequence is optimal. On the other hand, we show that both the 2-sweep algorithm based on the minimum-perimeter enclosing rectangle and the 2-sweep algorithm based on the minimum-perimeter enclosing parallelogram achieve a 4/pi approximate to 1.27 approximation of the optimal sweeping cost in this model. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Sweep-line approximation algorithm Figure of constant width Convex polygon

来源：评论

学校读者我要写书评

暂无评论

A note on approximating the min-max vertex disjoint paths on directed acyclic graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2011年第6期77卷 1054-1057页

作者： Wu, Bang Ye Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan

This paper shows that the FFTAS for the min-max disjoint paths problem on directed acyclic graphs by Yu et al. (2010) [7] can be improved by a rounding and searching technique. (C) 2010 Elsevier Inc. All rights reserved.

关键词： approximation algorithm Vertex disjoint paths Rounding FPTAS Directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

A new approximation algorithm for the nonpreemptive scheduling of independent jobs on identical parallel processors

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2007年第2期21卷 313-328页

作者： Paletta, Giuseppe Pietramala, Paolamaria Univ Calabria Dipartimento Econ & Stat I-87036 Cosenza Italy Univ Calabria Dipartimento Matemat I-87036 Cosenza Italy

We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively combines partial solutions to the problem. The worst-case performance ratio of the algorithm is (z+ 1)/(z) - (1)/(mz), where z is the number of initial partial solutions that are obtained by partitioning the set of jobs into z families of subsets which satisfy suitable properties. The computational behavior of our worst-case performance ratio provided encouraging results on three families of instances taken from the literature.

关键词： optimization scheduling approximation algorithm worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

A 4/3-approximation algorithm for cassette packing in steel industry

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2007年第5期24卷 715-724页

作者： Hwang, Hark-Chin Chosun Univ Dept Ind Engn Kwangju 501759 South Korea

In packing steel products of coils into cassettes, we need to consider both the width and weight capacity of cassettes. Each coil has weight in (0, 1/3] and width in (1/6, 1/3] when scaling both the weight and width capacities to 1. With the objective of minimizing the number of cassettes to pack the coils, the problem is modeled by two-dimensional vector packing. To efficiently pack the coils having sizes specified by the ranges, we develop a 4/3-approximation algorithm.

关键词： two-dimensional vector packing approximation algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

A simple linear time approximation algorithm for multi-processor job scheduling on four processors

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2007年第1期13卷 33-45页

作者： Huang, Jingui Chen, Jianer Chen, Songqiao Wang, Jianxin Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China

Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P (4)|fix|C (max), which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.

关键词： multi-processor job scheduling approximation algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：