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

IEEE International Conference on System, Man, and Cybernetic

作者： Lin, Chun-Cheng Yu, Chang-Sung Chang, Yin-Yih Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan Natl Taiwan Univ Dept Business Adm Taipei Taiwan Fu Jen Catholic Univ Dept Informat Management Taipei Taiwan

ISBN: (纸本)9781424423835

In transfusion medicine, the process of preparing or separating blood components from the whole blood is essential because the indication for the use of unfractionated whole blood almost does not exist nowadays. Since blood is uneasily-collected and easily-perished, a blood center or a hospital blood bank might as well aggressively manage the volume of each blood component. so as to decrease any waste. We assume that the process of blood component preparation can be underlaid by a so-called blood component tree, where each vertex representing a blood component with a certain value is derived from its parent vertex. Initially given a certain amount of the root blood component in a blood component tree (noticing that the amount of every other blood component is zero initially), the blood component preparation problem is concerned with finding the assignment of amount of each blood component such that the total value is maximized while satisfying the demand limit of every blood component. In this paper, we propose a linear time algorithm (in the size of vertices) for efficiently coping with the concerned problem, which also can be modeled as a linear program. Some theoretical analyses are included in this paper.

关键词： dynamic programming design and analysis of algorithms blood component preparation

来源：评论

学校读者我要写书评

暂无评论

Optimal semi-online algorithms for machine covering

引用

THEORETICAL COMPUTER SCIENCE 2007年第1期372卷 69-80页

作者： Tan, Zhiyi Wu, Yong Zhejiang Univ Dept Math State Key Lab CAD&CG Hangzhou 310027 Peoples R China

This paper investigates the semi-online machine covering problems on m >= 3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both m - 1. If the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are 3 when m = 3, and m - 2 when m >= 4. (c) 2006 Elsevier B.V. All rights reserved.

关键词： scheduling design and analysis of algorithms semi-online competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Scheduling orders for multiple product types to minimize total weighted completion time

引用

DISCRETE APPLIED MATHEMATICS 2007年第8期155卷 945-970页

作者： Leung, Joseph Y. -T. Li, Haibing Pinedo, Michael New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business New York NY 10012 USA

We consider the problem of scheduling orders for multiple different product types in an environment with in dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the in dedicated machines;that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number ( >= 2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space. (C) 2006 Elsevier B.V. All rights reserved.

关键词： order scheduling approximation algorithms design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast gapped variants for Lempel-Ziv-Welch compression

引用

INFORMATION AND COMPUTATION 2007年第7期205卷 1012-1026页

作者： Apostolico, Alberto Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Georgia Inst Technol Coll Comp Atlanta GA 30318 USA

Variants of classical data compression paradigms by Ziv, Lempel, and Welch are proposed in which the phrases used in compression are selected among suitably chosen strings of intermittently solid and wild characters produced by the auto-correlation of the sourcestring. Adaptations and extensions of the classical ZL78 paradigm as implemented by Welch are developed along these lines, and they are easily seen to be susceptible of simple linear time implementation. Both lossy and lossless schemata are considered, and preliminary analyses of performance are attempted. (c) 2007 Elsevier Inc. All rights reserved.

关键词： data compression by textual substitution lossy compression Ziv-Lempel-Welch phrase parse pattern matching trie design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for finding a longest common increasing subsequence

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2007年第3期13卷 277-288页

作者： Chan, Wun-Tat Zhang, Yong Fung, Stanley P. Y. Ye, Deshi Zhu, Hong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Leicester Dept Comp Sci Leicester Leics England Fudan Univ Dept Comp Sci & Engn Shanghai Peoples R China

We study the problem of finding a longest common increasing subsequence (LCIS) of multiple sequences of numbers. The LCIS problem is a fundamental issue in various application areas, including the whole genome alignment. In this paper we give an efficient algorithm to find the LCIS of two sequences in O(min(r log l, nl +r) log log n+Sort(n)) time where n is the length of each sequence and r is the number of ordered pairs of positions at which the two sequences match, e is the length of the LCIS, and Sort(n) is the time to sort n numbers. For in sequences where m >= 3, we find the LCIS in O(min(mr(2), r log l log(m) r) + ***(n)) time where r is the total number of m-tuples of positions at which the m sequences match. The previous results find the LCIS of two sequences in O(n(2)) and O(nl log log n+Sort(n)) time. Our algorithm is faster when r is relatively small, e.g., for r < min(n(2)/(log l log log n), nl/ log l).

关键词： design and analysis of algorithms longest common increasing subsequence

来源：评论

学校读者我要写书评

暂无评论

Motif discovery by monotone scores

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 695-706页

作者： Apostolico, Alberto Pizzi, Cinzia Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

The detection of frequent patterns such as motifs and higher aggregates is of pat-amount interest in biology and invests many other applications of automated discovery. The problem with its variants is usually plagued with computational burden. A related difficulty is posed by the fact, that due to the sheer mole of candidates, the tables and indices at the outset tend to be bulky, unmanageable, and ultimately uninformative. For solid patterns, it is possible to compact the size of statistical indices by resort to certain monotonicities exhibited by popular scores. The savings come from the fact that these monotonicities enable one to partition the candidate over-represented words into families in such a way that it suffices to consider and weigh only one candidate per family. In this paper, we study the problem of extracting, from given source x and error threshold k, substrings of x that occur unusually often in x within k substitutions or mismatches. Specifically, we assume that the input textstring x of n characters is produced by an i.i.d. source. and design efficient methods for computing the probability and expected number of occurrences for substrings of x with (either exactly or up to) k mismatches. Two related schemes are presented. In the first one, an O(nk) time preprocessing of x is developed that supports the following subsequent query: for any substring w of x arbitrarily specified as input, the probability of occurrence of w in x within (either exactly or up to) k mismatches is reported in O(k(2)) time. In the second scheme, a length or length range is arbitrarily specified, and the above probabilities are computed for all substrings of x having length in that range, in overall O(nk) time. Further, monotonicity conditions are introduced and studied for the probability and expected frequency of a substring under extension, increased number of errors, or both. Over intervals of constant frequency count, these monotonicities translate to some of the sco

关键词： design and analysis of algorithms pattern matching pattern discovery motif over-represented word monotone score correction factor

来源：评论

学校读者我要写书评

暂无评论

An effcient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第2期193卷 408-418页

作者： Hsieh, Sun-Yuan Huang, Chao-Wen Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 70101 Taiwan

Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we efficiently solve two subtree-comparison problems on a set of phylogenetic trees which have practical applications to analyze the evolution and co-evolution genes clustering of genomic sequences. Let T-1, T-2, ..., T-k be a set of k phylogenetic trees such that the leaves of each tree are drawn from {1, 2, ..., n} and the leaves for two arbitrary trees are not necessary the same, where n is the maximum number of the leaves among the k trees. We present a linear-time algorithm to find all the leaf-agreement descendant subtrees. By further extending this result, we present a linear-time algorithm to find all the leaf-agreement isomorphic descendant subtrees. Based on our algorithms, a web-based system using input tree files from TreeBASE is also implemented. (C) 2007 Elsevier Inc. All rights reserved.

关键词： knowledge discovery tree pattern retrieval phylogenetic trees descendant subtrees web-based system TreeBASE design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

The interval-merging problem

引用

INFORMATION SCIENCES 2007年第2期177卷 519-524页

作者： Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

A closed interval is an ordered pair of real numbers [x, y], with x <= y. The interval [x,y] represents the set {i is an element of R\x <= i <= y}. Given a set of closed intervals J = {[a(1), b(1)], [a(2), b(2)]...., [a(k), b(k)]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(J) = {[x(1), y(1)], [x(2), y(2)],..., [x(j), y(j)]}, j <= k, such that the real numbers represented by J = boolean OR(k)(i=1) [a(i), b(i)] equal those represented by M (J) = boolean OR(j)(i=1) [x(i), y(i)]. In this paper, we show the problem can be solved in O(dlog d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of J. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(logd) parallel time using O(d/logd) processors on an EREW PRAM. (C) 2006 Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms parallel algorithms data structures interval-merging PRAM

来源：评论

学校读者我要写书评

暂无评论

Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期370卷 299-308页

作者： Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we consider two descendent subtree-comparison problems on phylogenetic trees. Given a set of k phylogenetic trees whose leaves are drawn from {1, 2,..., n} and the leaves for two arbitrary trees are not necessary the same, we first present a linear-time algorithm to final all the maximal leaf-agreement descendent subtrees. Based on this result, we also present a linear-time algorithm to find all the maximal leaf-agreement isomorphic descendent subtrees. (c) 2006 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms phylogenetic trees maximal leaf-agreement descendent subtrees maximal leaf-agreernent isomorphic descendent subtrees

来源：评论

学校读者我要写书评

暂无评论

On computing longest paths in small graph classes

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2007年第5期18卷 911-930页

作者： Uehara, Ryuhei Uno, Yushi JAIST Sch Informat Sci Dept Informat Proc Ishikawa Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes.

关键词： algorithmic graph theory design and analysis of algorithms graph classes longest path problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：