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

randomized on-line and semi-on-line scheduling on identical machines

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2003年第1期20卷 31-40页

作者： He, Y Tan, ZY Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

This paper considers on-line and semi-on-line scheduling problems on m parallel machines with objective to maximize the minimum load. For on-line version, we prove that algorithm Random is an optimal randomized algorithm on two machines, and derive a new randomized upper bound for general m machines which significantly improves the known upper bound. For semi-on-line version with non-increasing job processing times, we show that LS algorithm is an optimal deterministic algorithm for two and three machine cases. We further present an optimal randomized algorithm RLS for two machine case.

关键词： on-line scheduling analysis of algorithm competitive ratio randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Arc-disjoint paths in expander digraphs

引用

SIAM JOURNAL ON COMPUTING 2003年第2期32卷 326-344页

作者： Bohman, T Frieze, A Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

Given a digraph D=(V,A) and a set of kappa pairs of vertices in V, we are interested in finding, for each pair (x(i),y(i)), a directed path connecting x(i) to y(i) such that the set of kappa paths so found is arc-disjoint. For arbitrary graphs the problem is NP-complete, even for kappa=2. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and the degree r is sufficiently large, then all sets of kappa=Omega (n/log n) pairs of vertices can be joined. This is within a constant factor of best possible.

关键词： edge disjoint paths expander digraphs randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient video similarity measurement with video signature

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2003年第1期13卷 59-74页

作者： Cheung, SCS Zakhor, A Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

The proliferation of video content on the Web makes similarity detection an indispensable tool in Web data management, searching, and navigation. In this paper, we propose a number of algorithms to efficiently measure video similarity. We define video as a set of frames, which are represented as high dimensional vectors in a feature space. Our goal is to measure ideal video similarity (IVS), defined as the percentage of clusters of similar frames shared between two video sequences. Since IVS is too complex to be deployed in large database applications, we approximate it with Voronoi video similarity (VVS), defined as the volume of the intersection between Voronoi cells of similar clusters. We propose a class of randomized algorithms to estimate VVS by first summarizing each video with a small set of its sampled frames, called the video signature (ViSig), and then calculating the distances between corresponding frames from the two ViSigs. By generating samples with a probability distribution that describes the video statistics, and ranking them based upon their likelihood of making an error in the estimation, we show analytically that ViSig can provide an unbiased estimate of IVS. Experimental results on a large dataset of Web video and a set of MPEG-7 test sequences with artificially generated similar versions are provided to demonstrate the retrieval performance of our proposed techniques.

关键词： randomized algorithm video similarity video summarization Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

Fast concurrent access to parallel disks

引用

algorithmICA 2003年第1期35卷 21-55页

作者： Sanders, P Egner, S Korst, J Max Planck Inst Comp Sci D-66123 Saarbrucken Germany Philips Res Labs NL-5656 AA Eindhoven Netherlands

High performance applications involving large data sets require the efficient and flexible use of multiple disks. In an external memory machine with D parallel, independent disks, only one block can be accessed on each disk in one I/O step. This restriction leads to a load balancing problem that is perhaps the main inhibitor for the efficient adaptation of single-disk external memory algorithms to multiple disks. We solve this problem for arbitrary access patterns by randomly mapping blocks of a logical address space to the disks. We show that a shared buffer of O(D) blocks suffices to support efficient writing. The analysis uses the properties of negative association to handle dependencies between the random variables involved. This approach might be of independent interest for probabilistic analysis in general. If two randomly allocated copies of each block exist, N arbitrary blocks can be read within [N/D] + 1 I/O steps with high probability. The redundancy can be further reduced from 2 to 1 + 1/r for any integer r without a big impact on reading efficiency. From the point of view of external memory models, these results rehabilitate Aggarwal and Vitter's "single-disk multi-head" model [1] that allows access to D arbitrary blocks in each I/O step. This powerful model can be emulated on the physically more realistic independent disk model [2] with small constant overhead factors. Parallel disk external memory algorithms can therefore be developed in the multi-head model first. The emulation result can then be applied directly or further refinements can be added.

关键词： randomized algorithm scheduling load balancing external memory

来源：评论

学校读者我要写书评

暂无评论

Minimizing flow time nonclairvoyantly

引用

JOURNAL OF THE ACM 2003年第4期50卷 551-567页

作者： Kalyanasundaram, B Pruhs, KR Georgetown Univ Dept Comp Sci Washington DC 20057 USA Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15260 USA

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average flow time. This is the classic CPU scheduling problem faced by time-sharing operating systems where preemption is allowed. It is easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst n-competitive, where n is the number of jobs. Yet there was no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably O(n(1-epsilon)). In this article, we give a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio O(log n log log n) against an oblivious adversary. RMLF is a slight variation of the multilevel feedback (MLF) algorithm used by the UNIX operating system, further justifying the adoption of this algorithm. It is known that every randomized nonclairvoyant algorithm is Omega(log n)-competitive, and that every deterministic nonclairvoyant algorithm is Omega(n(1/3))-competitive.

关键词： scheduling resource augmentation flow time shortest elapsed time first multilevel feedback randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Early termination in sparse interpolation algorithms

引用

JOURNAL OF SYMBOLIC COMPUTATION 2003年第3-4期36卷 365-400页

作者： Kaltofen, E Lee, ES N Carolina State Univ Dept Math Raleigh NC 27695 USA Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

A probabilistic strategy, early termination, enables different interpolation algorithms to adapt to the degree or the number of terms in the target polynomial when neither is supplied in the input. In addition to dense algorithms, we implement this strategy in sparse interpolation algorithms. Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms. The racing algorithms can be embedded as the univariate interpolation substep within Zippel's multivariate method. In addition, we experimentally verify some heuristics of early termination, which make use of thresholds and post-verification. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： early termination sparse polynomial black box polynomial interpolation sparse interpolation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving traveling salesman problem with Nested Queue-Jumping algorithm

Solving traveling salesman problem with Nested Queue-Jumping...

引用

25th International Conference on Information Technology Interfaces

作者： Zhai, DH Jin, F SW Jiaotong Univ Sch Comp & Comp Engn Chengdu 610031 Peoples R China

ISBN: (纸本)9539676967

This paper presents a new approximate algorithm Nested Queue-Jumping algorithm (NQJA) to solve traveling salesman problem. The proposed algorithm incorporates the thoughts of heuristic algorithm, randomized algorithm and local optimization. Numerical results show that to the small-scale instances, using Queue-Jumping algorithm (QJA) directly can obtain the known optimal solution with a large probability. In the case of large-scale instances, NQJA generates high-quality solution compared to well know heuristic methods. Moreover, the shortest tour to China 144 TSP found by NQJA is shorter than the known optimal tour. It can be a very promising alternative for finding a solution to the TSP. NQJA is specially devised for TSP, But its thought can give elicitation for other NP-hard combinatorial optimization problems.

关键词： traveling salesman problem Nested Queue-Jumping Agorithm (NQJA) Queue-Jumping algorithm (QJA) randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for on-line scheduling problems: how low can't you go?

引用

OPERATIONS RESEARCH LETTERS 2002年第2期30卷 89-96页

作者： Stougie, L Vestjens, APA Tech Univ Eindhoven Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands CWI NL-5600 MB Eindhoven Netherlands CQM Eindhoven Netherlands

We prove lower bounds on the competitive ratio of randomized algorithms for several on-line scheduling problems. The main result is a bound of e/(e - 1) for the on-line problem with objective minimizing the sum of completion times of jobs that arrive over time at their release times and are to be processed on a single machine, This lower bound shows that a randomized algorithm designed in Chekuri et al. (Proceedings of the Eighth ACM-SIAM Symposium on Discrete algorithms, 1997, 609 -618) is a best possible randomized algorithm for this problem. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line scheduling competitive analysis randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Discovering affine equalities using random interpretation

引用

ACM SIGPLAN NOTICES 2003年第1期38卷 74-84页

作者： Gulwani, S Necula, GC Univ Calif Berkeley Berkeley CA 94720 USA

We present a new polynomial-time randomized algorithm for discovering affine equalities involving variables in a program. The key idea of the algorithm is to execute a code fragment on a few random inputs, but in such a way that all paths are covered on each run. This makes it possible to rule out invalid relationships even with very few runs. The algorithm is based on two main techniques. First, both branches of a conditional are executed on each run and at joint points we perform an affine combination of the joining states. Secondly, in the branches of an equality conditional we adjust the data values on the fly to reflect the truth value of the guarding boolean expression. This increases the number of affine equalities that the analysis discovers. The algorithm is simpler to implement than alternative deterministic versions, has better computational complexity, and has an extremely small probability of error for even a small number of runs. This algorithm is an example of how randomization can provide a trade-off between the cost and complexity of program analysis, and a small probability of unsoundness.

关键词： algorithms theory verification affine relationships linear equalities random interpretation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Polynomial factorization: a success story 03

Polynomial factorization: a success story

引用

Proceedings of the 2003 international symposium on Symbolic and algebraic computation

作者： Erich Kaltofen North Carolina State University Raleigh NC

ISBN: (纸本)9781581136418

The problem of factoring a polynomial in a single or severalvariables over a finite field, the rational numbers or the complexnumbers is one of the success stories in the discipline of symboliccomputation. In the early 1960s implementors investigated theconstructive methods known from classical algebra books, but--withthe exception of Gauss's distinct degree factorizationalgorithm--found the algorithms quite inefficient in practice [16].The contributions in algorithmic techniques that have been madeover the next 40 years are truly a hallmark of symbolic *** early pioneers, Berlekamp, Musser, Wang, Weinberger,Zassenhaus and others applied new ideas like randomization, thateven before the now famous algorithms for primality testing byRabin and Strassen, and like generic programming with coefficientdomains as abstract data classes, and they introduced the powerfulHensel lifting lemma to computer algebra. We note that whilede-randomization for integer primality testing has beenaccomplished recently [1], the same remains open for the problem ofcomputing a root of a polynomial modulo a large prime [12, ResearchProblem 14.48].Polynomial-time complexity for rational coefficients wasestablished in the early 1980s by the now-famous lattice basisreduction algorithm of A. Lenstra, H. W. Lenstra, Jr., and ***ász. The case of many variables first became anapplication of the DeMillo and Lipton/Schwartz/Zippel lemma [30]and then triggered a fundamental generalization from the standardsparse (distributed) representation of polynomials to the one bystraight line and black box programs [11, 17, 19]. Effectiveversions of the Hilbert irreducibility theorem are needed for theprobabilistic analysis, which serendipitously later have alsoplayed a role in the PCP characterization of NP[2]. Unlike many other problems in commutative algebra andalgebraic geometry, such as algebraic system solving, thepolynomial factoring problem is of probabilistic polynomial-timeco

关键词： polynomial factorization symbolic/numeric hybrid method straight line program lattice basis reduction randomized algorithm black box polynomial

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：