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

average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第8期66卷 1090-1102页

作者： Li, Keqin SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound;however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times. (C) 2005 Elsevier Inc. All rights reserved.

关键词： average-case performance largest-task-first level-by-level scheduling mesh connected multicomputer system precedence constraint processor allocation random parallel task two-dimensional buddy system

来源：评论

学校读者我要写书评

暂无评论

Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks

引用

ACM Journal of Experimental Algorithmics 2008年第pp1–24期12卷 1-24页

作者： Li, Keqin State University of New York New Paltz United States Department of Computer Science State University of New York New Paltz NY 12561 United States

We investigate the problem of online routing and wavelength assignment and the related throughput maximization problem in wavelength division multiplexing optical networks. It is pointed out that these problems are highly inapproximable, that is, the competitive ratio of any algorithm is at least a polynomial. We evaluate the average-case performance of several online algorithms, which have no knowledge of future arriving connection requests when processing the current connection request. Our experimental results on a wide range of optical networks demonstrate that the average-case performance of these algorithms are very close to optimal. © 2008 ACM.

关键词： average-case performance Competitive ratio Online algorithm Optical network Routing Wavelength assignment Wavelength division multiplexing

来源：评论

学校读者我要写书评

暂无评论

A SWEEPLINE ALGORITHM TO SOLVE THE 2-CENTER PROBLEM

引用

INFORMATION PROCESSING LETTERS 1994年第4期49卷 171-177页

作者： HUANG, NF HUANG, CH WANG, YL NATL TSING HUA UNIV INST COMP SCIHSINCHU 300TAIWAN NATL TAIWAN INST TECHNOL DEPT INFORMAT MANAGEMENTTAIPEI 100TAIWAN

Proposed in this paper is a sweepline algorithm to solve the two-center problem with time complexity. Also analyzed is the average-case time complexity of the proposed algorithm. Compared with the best known algorithm to solve the two-center problem, the proposed algorithm is easier to implement and the average-case time complexity is easier to analyze.

关键词： ALGORITHMS average-case performance COMPUTATIONAL GEOMETRY GEOMETRIC LOCATION PROBLEM 2-CENTER PROBLEM

来源：评论

学校读者我要写书评

暂无评论

average-case ANALYSIS OF THE MODIFIED HARMONIC ALGORITHM

引用

ALGORITHMICA 1989年第4期4卷 519-533页

作者： RAMANAN, P TSUGA, K 1. Department of Computer Science University of California 93106 Santa Barbara CA USA

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i} _i=1 ^k where theN _i's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i. LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_n _→∞E(max(_f ₁,f ₂))/n = lim_n→∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.

关键词： Bin packing Approximation algorithm On-line algorithm Worst-case performance average-case performance

来源：评论

学校读者我要写书评

暂无评论

average-case ANALYSIS OF THE SMART NEXT FIT ALGORITHM

引用

INFORMATION PROCESSING LETTERS 1989年第5期31卷 221-225页

作者： RAMANAN, P UNIV CALIF SANTA BARBARA DEPT COMP SCISANTA BARBARACA 93106

We present the Smart Next Fit algorithm for on-line bin packing, which is obtained by slightly modifying the Next Fit algorithm. For any list of items, this algorithm uses the smallest number of bins among all on-line algorithms that have only one active bin at any time. We analyze its average-case performance when the item sizes are uniformly distributed over (0, b), b less than or equal to 1. For b less than or equal to 1/2, the Smart Next Fit algorithm behaves exactly like the Next Fit algorithm. For 1/2 < b less than or equal to 1, its average-case performance is significantly better than that of Next Fit. For b = 1, its average-case performance rate is 1.2274113..., compared to 1.333... for Next Fit. Its average-case performance is better than that of any known constant-space algorithm.

关键词： Bin packing approximation algorithms on-line algorithms worst-case performance average-case performance

来源：评论

学校读者我要写书评

暂无评论

average-case ANALYSIS OF CUTTING AND PACKING IN 2 DIMENSIONS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1990年第2期44卷 134-144页

作者： COFFMAN, EG SHOR, PW AT&T BELL LABS 20-1155MURRAY HILLNJ 07974 USA

Stock-cutting and packing in two dimensions is a source of problems of great practical significance. Much has been written on the subject, including several surveys, but the focus of the mathematically oriented research has been largely on combinatorial optimization and worst-case analysis. Recently, substantial progress has been made in the average-case analysis of algorithms for two-dimensional packing. This paper reviews selected, illustrative results in this area of research, and discusses desirable extensions and open problems. Several cutting and packing algorithms are defined and the results of their probabilistic analysis reported. From the presentation of this material it is clear that the field is still in early stages of development; the algorithms and probability models tend to be simplistic, and estimates of performance are far more common that exact measures. In spite of these limitations, valuable and in some cases unexpected insights have emerged. [ABSTRACT FROM AUTHOR]

关键词： asymptotic analysis average-case performance cutting and packing algorithms trim loss analysis Two-dimensional cutting two-dimensional packing

来源：评论

学校读者我要写书评

暂无评论

Downlink data transmission scheduling algorithms in wireless networks

引用

SIMULATION MODELLING PRACTICE AND THEORY 2011年第6期19卷 1427-1444页

作者： Li, Keqin SUNY Coll New Paltz Dept Comp Sci New Paltz NY 12561 USA

The problem of downlink data transmission scheduling in wireless networks is studied. It is pointed out that every downlink data transmission scheduling algorithm must have two components to solve the two subproblems of power assignment and transmission scheduling. Two types of downlink data transmission scheduling algorithms are proposed. In the first type, power assignment is performed before transmission scheduling. In the second type, power assignment is performed after transmission scheduling. The performance of two algorithms of the first type which use the equal power allocation method are analyzed. It is shown that both algorithms exhibit excellent worst-case performance and asymptotically optimal average-case performance under the condition that the total transmission power is equally allocated to the channels. In general, both algorithms exhibit excellent average-case performance. It is demonstrated that two algorithms of the second type perform better than the two algorithms of the first type due to the equal time power allocation method. Furthermore, the performance of our algorithms are very close to the optimal and the room for further performance improvement is very limited. It is shown that all the above algorithms can be extended to schedule downlink data transmissions with parallel channels. It is also shown that the simple sequential scheduling algorithm is optimal if the total transmission power is equally allocated to the channels. As an extra contribution, an M/G/1 queueing model for the FCFS queueing discipline is established, and it is observed that increasing the number of channels has more impact on the reduction of the average response time than increasing the total transmission power. (C) 2010 Elsevier B.V. All rights reserved.

关键词： average-case performance Downlink data transmission Power assignment Simulation Transmission scheduling Wireless network Worst-case performance

来源：评论

学校读者我要写书评

暂无评论

performance evaluation of heuristic algorithms for wavelength assignment in WDM optical networks

Performance evaluation of heuristic algorithms for wavelengt...

引用

33rd International Conference on Parallel Processing

作者： Li, KQ SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

ISBN: (纸本)0769521983

Given a set of connection requests in a WDM optical network and a designated lightpath for each connection request, the wavelength assignment problem is to assign a wavelength to each lightpath in such a way that light-paths sharing common links are assigned different wavelengths and the number of wavelengths used is minimized. The main result of the paper is to show that there exist simple heuristic wavelength assignment algorithms whose average-case performance is very close to the optimum. Our strategy is to convert wavelength assignment on an optical network with randomly generated connection requests into vertex coloring on a random lightpath graph.

关键词： average-case performance heuristic mesh optical network random network vertex coloring wavelength assignment wavelength division multiplexing

来源：评论

学校读者我要写书评

暂无评论

On Minimum Cost Recovery from System Deadlock

引用

IEEE Transactions on Computers 1979年第9期C-28卷 671-677页

作者： Leung, Joseph Y. T. Lai, Edmund K. Department of Electrical Engineering and Computer Science Northwestern University Evanston IL 60201 United States

In this paper we consider the problem of finding a minimum cost deadlock recovery. We show that the problem is NP-complete and hence an efficient algorithm is unlikely to exist for this problem. We propose three fast heuristics and analyze their worst case performance relative to optimal solutions. Finally, we perform some simulation tests to get a feel for the average performance of these heuristics. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.

关键词： Approximation algorithms NP-complete problems average-case performance minimum cost deadlock recovery system deadlock time complexity worst case performance

来源：评论

学校读者我要写书评

暂无评论

average-case ANALYSIS OF ALGORITHMS FOR MATCHINGS AND RELATED PROBLEMS

引用

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY 1994年第6期41卷 1329-1356页

作者： MOTWANI, R Stanford Univ. Stanford CA

We analyze the behavior of augmenting paths in random graphs. Our results show that in almost every graph, any nonmaximum 0-1 flow admits a short augmenting path. This enables us to prove that augmenting-path algorithms, that are fast in the worst case, also perform exceedingly well on the average. In particular, we show that the O(square-root\V\\E\) algorithms for bipartite and general matchings run in almost linear time with high probability. It is also shown that the expected running time of the matching algorithms is O(\E\) on input graphs chosen uniformly at random from the set of all graphs. We establish that the permanent of almost every bipartite graph can be approximated in polynomial time. We extend our results to the analysis of the running time of Dinic's algorithm for finding factors of graphs.

关键词： average-case performance FACTORS MAXIMUM MATCHINGS NETWORK FLOW PERMANENTS PROBABILISTIC ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：