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

average case analysis of bounded space bin packing algorithms

ALGORITHMICA 2008年第1期50卷 72-97页

作者： Naaman, Nir Rom, Raphael Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.

关键词： bin packing average case analysis algorithms dscrete item size distribution bounded space

来源：评论

学校读者我要写书评

暂无评论

average case analysis of dynamic geometric optimization

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1996年第1期6卷 45-68页

作者： Eppstein, D UNIV CALIF IRVINE DEPT INFORMAT & COMP SCI IRVINE CA 92717 USA

We maintain the maximum spanning tree of a planar point set, as points are inserted or deleted, in O(log(3) n) expected time per update in Mulmuley's average-case model of dynamic geometric computation. We use as subroutines dynamic algorithms for two other geometric graphs: the farthest neighbor forest and the rotating caliper graph related to an algorithm for static computation of point set widths and diameters. We maintain the former graph in expected time O(log(2) n) per update and the latter in expected time O(log n) per update. We also use the rotating caliper graph to maintain the diameter, width,, and minimum enclosing rectangle of a point set in expected time O(logn) per update. A subproblem uses a technique for average-case orthogonal range search that may also be of interest.

关键词： dynamic geometric optimization maximum spanning tree farthest neighbor forest rotating caliper graph orthogonal range search average case analysis

来源：评论

学校读者我要写书评

暂无评论

average case analysis for tree labelling schemes

引用

THEORETICAL COMPUTER SCIENCE 2007年第3期378卷 271-291页

作者： Kao, Ming-Yang Li, Xiang-Yang Wang, Weizhao IIT Dept Comp Sci Chicago IL 60616 USA Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log(2) n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme 8 that has the optimal label length Theta (log n center dot log(H-n (T))), where H-n (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only. (c) 2007 Elsevier B.V. All rights reserved.

关键词： tree labelling average case analysis separator

来源：评论

学校读者我要写书评

暂无评论

average case analysis of DJ graphs

引用

JOURNAL OF DISCRETE ALGORITHMS 2006年第4期4卷 649-675页

作者： Blieberger, Johann Vienna Univ Technol Dept Comp Aided Automat 183-1Treitlstr 1 A-1040 Vienna Austria

Sreedhar et al. [V.C. Sreedhar, G.R. Gao, Y.-F. Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Trans. Program. Lang. Syst. 20 (2) (1998) 388-435;V.C. Sreedhar, Efficient program analysis using DJ graphs, PhD thesis, School of Computer Science, McGill University, Montreal, Quebec, Canada, 1995] have presented an elimination-based algorithm to solve data flow problems. A thorough analysis of the algorithm shows that the worst-case performance is at least quadratic in the number of nodes of the underlying graph. In contrast, Sreedhar reports a linear time behavior based on some practical applications. In this paper we prove that for goto-free programs, the average case behavior is indeed linear. As a byproduct our result also applies to the average size of the so-called dominance frontier. A thorough average case analysis based on a graph grammar is performed by studying properties of the j-edges in DJ graphs. It appears that this is the first time that a graph grammar is used in order to analyze an algorithm. The average linear time of the algorithm is obtained by classic techniques in the analysis of algorithms and data structures such as singularity analysis of generating functions and transfer lemmas. (C) 2005 Elsevier B.V. All rights reserved.

关键词： average case analysis Data flow analysis Dominator tree DJ graphs Dominance frontier

来源：评论

学校读者我要写书评

暂无评论

An average case analysis of a greedy algorithm for the on-line Steiner tree problem

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1996年第11期31卷 121-131页

作者： Tsai, YT Tang, CY Chen, YY Department of Computer Science National Tsing Hua University Hsinchu 300 Taiwan R.O.C.

This paper gives the average distance analysis for the Euclidean tree constructed by a simple greedy but efficient algorithm of the on-line Steiner tree problem. The algorithm accepts the data one by one following the order of input sequence. When a point arrives, the algorithm adds the shortest edge, between the new point and the points arriving already, to the previously constructed tree to form a new tree. We first show that, given n points uniformly on a unit disk in the plane, the expected Euclidean distance between a point and its j(th) (1 less than or equal to j less than or equal to n - 1) nearest neighbor is less than or equal to (5/3)root/j/n when n is large. Based upon this result, we show that the expected length of the tree constructed by the on-line algorithm is not greater than 4.34 times the expected length of the minimum Steiner tree when the number of input points is large.

关键词： analysis of algorithms on-line algorithms average case analysis on-line Steiner tree problems Euclidean space

来源：评论

学校读者我要写书评

暂无评论

average case analysis for tree labelling schemes

引用

16th International Symposium on Algorithms and Computations (ISAAC 2005)

作者： Kao, Ming-Yang Li, Xiang-Yang Wang, Weizhao IIT Dept Comp Sci Chicago IL 60616 USA Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

ISBN: (纸本)3540309357

关键词： tree labelling average case analysis separator

来源：评论

学校读者我要写书评

暂无评论

average case analysis OF COMPRESSIVE MULTICHANNEL FREQUENCY ESTIMATION USING ATOMIC NORM MINIMIZATION 23

AVERAGE CASE ANALYSIS OF COMPRESSIVE MULTICHANNEL FREQUENCY ...

引用

23rd IEEE International Conference on Digital Signal Processing (DSP)

作者： Yang, Zai Eldar, Yonina C. Xie, Lihua Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Jiangsu Peoples R China Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

ISBN: (纸本)9781538668122;9781538668115

Compressive multichannel frequency estimation refers to the process of retrieving the frequency profile shared by multiple signals from their compressive samples. A recent approach to this problem relies on atomic norm minimization which exploits joint sparsity among the channels, is solved using convex optimization, and has strong theoretical guarantees. We provide in this paper an average-case analysis for atomic norm minimization by assuming proper randomness on the amplitudes of the frequencies. We show that the sample size per channel required for exact frequency estimation from noiseless samples decreases as the number of channels increases and is on the order of K log K (1 + 1/L log N), where K is the number of frequencies, L is the number of channels, and N is a fixed parameter proportional to the sampling window size and inversely proportional to the desired resolution.

关键词： Multichannel frequency estimation atomic norm minimization average case analysis compressed sensing

来源：评论

学校读者我要写书评

暂无评论

The relevant prefixes of coloured Motzkin walks: An average case analysis

引用

THEORETICAL COMPUTER SCIENCE 2010年第1期411卷 148-163页

作者： Merlini, D. Sprugnoli, R. Dipartimento Sistemi & Informat I-50134 Florence Italy

In this paper we study some relevant prefixes of coloured Motzkin walks (otherwise called coloured Motzkin words). In these walks, the three kinds of step can have alpha, beta and gamma colours, respectively. In particular, when alpha = beta = gamma = 1 we have the classical Motzkin walks while for alpha = gamma = 1 and beta = 0 we find the well-known Dyck walks. By using the concept of Riordan arrays and probability generating functions we find the average length of the relevant prefix in a walk of length n and the corresponding variance in terms of alpha, beta and gamma. This result is interesting from a combinatorial point of view and also provides an average case analysis of algorithms related to the problem of ranking and generating uniformly at random the coloured Motzkin words. (C) 2009 Elsevier B.V. All rights reserved.

关键词： average case analysis Coloured Motzkin walks Probability generating functions Random generation Ranking

来源：评论

学校读者我要写书评

暂无评论

A new average case analysis for completion time scheduling

引用

JOURNAL OF THE ACM 2006年第1期53卷 121-146页

作者： Scharbrodt, M Schickinger, T Steger, A Tech Univ Munich Inst Informat D-80290 Munich Germany ETH Inst Theoret Informat CH-8092 Zurich Switzerland

We present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio-which is a typical worst case notion-also within an average case analysis. We show that the classic SEPT scheduling strategy with 0(n) worst-case competitive ratio achieves an average of 0(l) under several natural distributions, among them the exponential distribution. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, Our result bridges the gap between worst case and average case performance guarantee.

关键词： theory algorithms scheduling theory average case analysis

来源：评论

学校读者我要写书评

暂无评论

An average case analysis of the minimum spanning tree heuristic for the power assignment problem

引用

RANDOM STRUCTURES & ALGORITHMS 2019年第1期55卷 89-103页

作者： de Graaf, Maurits Boucherie, Richard J. Hurink, Johann L. van Ommeren, Jan-Kees Thales Nederland BV Innovat Res & Technol POB 88 NL-1270 AB Huizen Netherlands Univ Twente Dept Appl Math Enschede Netherlands

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst-case approximation ratio of this heuristic is 2. We show that in Euclidean d-dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1](d), and the distance power gradient equals the dimension d, the minimum spanning tree-based power assignment converges completely to a constant depending only on d.

关键词： ad-hoc networks analysis of algorithms approximation algorithms average case analysis point processes power assignment range assignment

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：