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

Combining polynomial running time and fast convergence for the disk-covering method

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2002年第3期65卷 481-493页

作者： Lagergren, J KTH Stockholm Bioinformat Ctr Dept Numer Anal & Comp Sci S-10044 Stockholm Sweden

This paper treats polynomial-time algorithms for reconstruction of phylogenetic trees. The disc-covering method (DCM) presented by Huson et al. (J. Comput. Biol. 6 (3/4) (1999) 369) is a method that boosts the performance of phylogenetic tree construction algorithms. Actually, they gave two variations of DCM-Buneman. The first variation was guaranteed to recover the true tree with high probability from polynomial-length sequences (i.e. polynomial in the number of given taxa), but it was not proven to run in polynomial time. The second variation was guaranteed to run in polynomial time. However, it is a heuristic in the sense that it was not proven to recover the true tree with high probability from polynomial-length sequences. We present an improved DCM. The difference between our improved DCM and the heuristic variation of the original DCM is marginal. The main contribution of this paper is the analysis of the algorithm. Our analysis shows that the improved DCM combines the desirable properties of the two variations of the original DCM. That is, it runs in polynomial time and it recovers the true tree with high probability from polynomial-length sequences. Moreover, this is true when the improved DCM is applied to the Neighbor-Joining, the Buneman, as well as the Agarwala algorithm. A key observation for the result of Huson et al. was that threshold graphs of additive distance functions are chordal. We prove a chordal graph theorem concerning minimal triangulations of threshold graphs constructed from distance functions which are close to being additive. This theorem is the key observation behind our improved DCM and it may be interesting in its own right. (C) 2002 Published by Elsevier Science (USA).

关键词： data control memory Heuristics algorithms Chord Polynomial analysis of algorithm Runtime distance function Polynomial time

来源：评论

学校读者我要写书评

暂无评论

Incremental Facility Location Problem and Its Competitive algorithms

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第3期20卷 307-320页

作者： Dai, Wenqiang Zeng, Xianju Univ Elect Sci & Technol China Sch Management & Econ Chengdu 610054 Sichuan Peoples R China City Univ Hong Kong Dept Management Kowloon Hong Kong Peoples R China

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F-1 subset of F-2 subset of...subset of F-n, where each F-k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c-competitive if the cost of each F-k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8 alpha, where alpha is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384: 126-135, 2007), we obtain the competitive ratio 16 + 8 root 3 + epsilon. The second algorithm has the competitive ratio Delta + 1, where Delta is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Delta <= 8 alpha - 1.

关键词： analysis of algorithm Online algorithm Competitive ratio Facility location

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling of parallel machines to minimize total completion times

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第9期36卷 2647-2652页

作者： Liu, Peihai Lu, Xiwen E China Univ Sci & Technol Sch Sci Shanghai 200237 Peoples R China

In this paper, we consider the scheduling problem on identical parallel machines, in which jobs are arriving over time and preemption is not allowed. The goal is to minimize the total completion times. According to the idea of the Delayed-SPT algorithm proposed by Hoogeven and Vestjens [Optimal on-line algorithms for single-machine scheduling. In: Proceedings 5th international conference on integer programming and combinatorial optimization (IPCO). Lecture notes in computer science, vol. 1084. Berlin: Springer;1996. p. 404-14], we give an on-line algorithm for the scheduling problem on m identical parallel machines. We show that this algorithm is 2-competitive and the bound is tight. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Parallel machine scheduling analysis of algorithm On-line algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF SORTING IN MAGNETIC-BUBBLE MEMORY-SYSTEMS

引用

IEEE TRANSACTIONS ON COMPUTERS 1980年第7期29卷 553-563页

作者： CHUNG, KM LUCCIO, F WONG, CK IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598 UNIV PISA IST SCI INFORMAZI-56100 PISAITALY

In this paper the problem of sorting in various models of magnetic bubble memory systems is studied. Three basic parameters are of interest, namely, the number of steps to sort, the number of switches required, and the number of control states necessary for the switches. Several sorting algorithms are proposed with respective running times essentially n2, n/2, 1/2 n log2 n, 7/2 n, n log2n, respective numbers of switches essentially, 1, n, 2√n, 2√nlog2n , 1og2n, and respective numbers of control states essentially, 3, 2, 1/8 log2n, 1/8 log2n, and 3 log2n.

关键词： analysis of algorithm control states magnetic bubble memories sorting switches

来源：评论

学校读者我要写书评

暂无评论

COMPARISON OF STATISTICAL METHODS OF RADIATION MONITORING

引用

ATOMIC ENERGY 2009年第3期107卷 209-217页

作者： Shumakov, A. V. Kasatkin, V. P. Dukhov All Russia Res Inst Automat Moscow Russia

The results of a Monte-Carlo simulation of algorithms for statistical analysis of information from detectors in radiation monitors, recording the presence of random, short-time, weak radioactive radiation, are presented. The Neyman-Pearson test and likelihood ratio, moving average, digital recursive filter, a priori probability, half-sums, and relative dispersion methods are examined. The results of a comparative analysis of the algorithms and the investigation of the possibilities and conditions for realizing their maximum possibilities are presented. The analysis has shown that the moving average method has advantages. It can be replaced by the similarity ratio method in the event of a Poisson distribution and the a priori probability method in the event of a Gaussian distribution. For an average background of not more than 5 with a large separation the moving average and similarity ratio methods are best. Otherwise the digital recursive filter method is best. The best results are obtained by combining the detection method with the moving average method together with likelihood ratio and a priori probability methods.

关键词： Monte Carlo technique algorithms inspection methods probability methods Probability Gaussian distribution recursive filters Poisson distribution Radiation monitoring likelihood ratio analysis of algorithm Moving average

来源：评论

学校读者我要写书评

暂无评论

3-Partitioning problems for maximizing the minimum load

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2002年第1期6卷 67-80页

作者： Chen, SP He, Y Lin, G Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Univ Waterloo Dept Comp Sci Waterloo ON N2L 3G1 Canada McMaster Univ Dept Comp & Software Hamilton ON L8S 4L8 Canada

The optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems are considered in this paper. For the objective to maximize the minimum load of the m subsets, it is shown that the MODIFIED LPT a... 详细信息

关键词： partitioning scheduling analysis of algorithm worst case performance ratio kernel

来源：评论

学校读者我要写书评

暂无评论

Extension of algorithm list scheduling for a semi-online scheduling problem

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2007年第1期15卷 97-104页

作者： He, Yong Dosa, Gyoergy Pannon Univ Dept Math Veszprem Hungary

A general algorithm, called ALG, for online and semi-online scheduling problem Pm || C-max with m >= 2 is introduced. For the semi-online version, it is supposed that all job have their processing times within the interval [p, rp], where p > 0, 1 < r <= m/m - 1. ALG is a generalization of LS and is optimal in the sense that there is not an algorithm with smaller competitive ratio than that of ALG.

关键词： analysis of algorithm scheduling semi-online competitive ratio

来源：评论

学校读者我要写书评

暂无评论

algorithms for semi on-line multiprocessor scheduling problems

引用

Journal of Zhejiang University Science 2002年第1期3卷 60-64页

作者：杨启帆谈之奕姚恩瑜何勇 DepartmentofMathematics ZhejiangUniversityHangzhou310027China DepartmentofSystemScience&Engeering ZhejiangUniversityHangzhou310027China

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.

关键词： analysis of algorithm on\|line scheduling worst\|case ratio

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL algorithm FOR COMPUTING THE REPETITIONS IN A WORD

引用

INFORMATION PROCESSING LETTERS 1981年第5期12卷 244-250页

作者： CROCHEMORE, M Laboratoire d'Informatique Université de Haute - Normandie BP 67 76130 Mont-Saint-Aignan France

Fibonacci words are among those words containing a repetition, i.e., at least 2 consecutive equal factors. Main and Lorentz have introduced an algorithm to find one repetition or square in a word. In the word aababba, for example, abab is a repetition or square. An algorithm is presented to compute all the repetitions of factors in a word. The algorithm uses an improved version of the well-known partitioning technique. Proofs are presented to demonstrate that the new algorithm, referred to as REP, is optimal in the class of algorithms computing all the repetitions of a word. Proofs also are presented to show that an associated procedure, REPMAX, is optimal in the class of algorithms computing all the maximal repetitions of a word.

关键词： analysis of algorithm optimality partitioning repetitions in words

来源：评论

学校读者我要写书评

暂无评论

On Weighted Depths in Random Binary Search Trees

引用

JOURNAL OF THEORETICAL PROBABILITY 2018年第4期31卷 1929-1951页

作者： Aguech, Rafik Amri, Anis Sulzbach, Henning King Saud Univ Coll Sci Dept Stat & Operat Res POB 2455 Riyadh 11451 Saudi Arabia Univ Monastir Ave Taher HaddedBP 56 Monastir 5000 Tunisia Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England

Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133-141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.

关键词： analysis of algorithm Data structures Binary search trees Central limit theorems Contraction method Random probability measures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：