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

Efficient randomized algorithms for the repeated median line estimator

ALGORITHMICA 1998年第2期20卷 136-150页

作者： Matousek, J Mount, DM Netanyahu, NS UNIV MARYLAND DEPT COMP SCI COLLEGE PK MD 20742 USA UNIV MARYLAND INST ADV COMP STUDIES COLLEGE PK MD 20742 USA UNIV MARYLAND CTR AUTOMAT RES COLLEGE PK MD 20742 USA NASA GODDARD SPACE FLIGHT CTR CTR EXCELLENCE SPACE DATA & INFORMAT SCI GREENBELT MD 20771 USA

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Recently there has been a great deal of interest is robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator, One problem with robust estimators is that achieving high breakdown points (near 50%) has proved to be computationally demanding. In this paper we present the best known theoretical algorithm and a practical subquadratic algorithm for computing a 50% breakdown point line estimator, the Siegel or repeated median line estimator. We first present an O(n log n) randomized expected-time algorithm, where la is the number of given points. This algorithm relies, however, on sophisticated data structures. We also present a very simple O(n log(2) n) randomized algorithm for this problem, which uses no complex data structures. We provide empirical evidence that, for many realistic input distributions, the running time of this second algorithm is actually O (n log n) expected time.

关键词： repeated median estimator line fitting robust estimators randomized algorithms computational geometry

来源：评论

学校读者我要写书评

暂无评论

A decomposition theorem for task systems and bounds for randomized server problems

引用

SIAM JOURNAL ON COMPUTING 2000年第5期30卷 1624-1661页

作者： Blum, A Karloff, H Rabani, Y Saks, M Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel DIMACS Piscataway NJ USA Rutgers State Univ Dept Math Piscataway NJ 08854 USA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

A lower bound of Omega(root log k/log log k) is proved for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (having at least k + 1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of (log log k) for arbitrary metric spaces [H. J. Karlo, Y. Rabani, and Y. Ravid, SIAM J. Comput., 23 (1994), pp. 293-312] and more closely approaches the conjectured lower bound of ( log k). For the server problem on k + 1 equally spaced points on a line, which corresponds to a natural motion-planning problem, a lower bound of (log k/log log k) is obtained. The results are deduced from a general decomposition theorem for a simpler version of both the k-server and the metrical task system problems, called the pursuit-evasion game. It is shown that if a metric space M can be decomposed into two spaces M-L and M-R such that the distance between them is sufficiently large compared to their diameter, then the competitive ratio for this game on M can be expressed nearly exactly in terms of the ratios on each of the two subspaces. This yields a divide-and-conquer approach to bounding the competitive ratio of a space.

关键词： lower bounds randomized algorithms k-server task systems on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Online randomized multiprocessor scheduling

引用

ALGORITHMICA 2000年第2期28卷 173-216页

作者： Seiden, SS Max Planck Inst Informat D-66123 Saarbrucken Germany

The use of randomization in online multiprocessor scheduling is studied. The problem of scheduling independent jobs on tn machines online originates with Graham [16]. While the deterministic case of this problem has been studied extensively, little work has been done on the randomized case. For m = 2 a randomized 4/3-competitive algorithm was found by Bartal et al. A randomized algorithm for m greater than or equal to 3 is presented. It achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m = 3, 4, 5, 6, 7, respectively. These competitive ratios are less than the best deterministic lower bound for m = 3, 4, 5 and less than the best known deterministic competitive ratio for m = 3, 4, 5, 6, 7. Two models of multiprocessor scheduling with rejection are studied. The first is the model of Bartal et al. Two randomized algorithms for this model are presented. The first algorithm performs well for small m, achieving competitive ratios of 3/2, (7 + root 129)/10 < 1.83579, (5 + 2 root 22)/7 < 2.05441 for m = 2, 3, 4, respectively. The second algorithm outperforms the first for m greater than or equal to 5. It beats the deterministic algorithm of Bartal et al. for all m = 5,..., 1000. It is conjectured that this is true for all m. The second model differs in that preemption is allowed. For this model, randomized algorithms are presented which outperform the best deterministic algorithm for small m.

关键词： competitive analysis online algorithms randomized algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

Verification of identities

引用

SIAM JOURNAL ON COMPUTING 2000年第4期29卷 1155-1163页

作者： Rajagopalan, S Schulman, LJ IBM Corp Almaden Res Ctr San Jose CA 95114 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

We provide an O(n(2) log 1/delta) time randomized algorithm to check whether a given operation o : S X S --> S is associative (where n = \S\ and delta > 0 is the error probability required of the algorithm). We prove that (for any constant delta) this performance is optimal up to a constant factor, even if the operation is "cancellative." No sub-n(3) time algorithm was previously known for this task. More generally we give an O(n(c)) time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.

关键词： computer aided verification randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Nonmalleable cryptography

引用

SIAM JOURNAL ON COMPUTING 2000年第2期30卷 391-437页

作者： Dolev, D Dwork, C Naor, M Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel IBM Corp Almaden Res Ctr Div Res San Jose CA 95120 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Nonmalleable schemes for each of these three problems are presented. The schemes do not assume a trusted center;a user need not know anything about the number or identity of other system users. Our cryptosystem is the rst proven to be secure against a strong type of chosen ciphertext attack proposed by Racko and Simon, in which the attacker knows the ciphertext she wishes to break and can query the decryption oracle on any ciphertext other than the target.

关键词： cryptography cryptanalysis encryption authentication randomized algorithms nonmalleability chosen ciphertext security auction protocols commitment schemes zero-knowledge

来源：评论

学校读者我要写书评

暂无评论

Union and split operations on dynamic trapezoidal maps

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第3-4期17卷 153-163页

作者： Teillaud, M INRIA F-06902 Sophia Antipolis France

We propose algorithms to perform two new operations on an arrangement of line segments in the plane, represented by a trapezoidal map: the split of the map along a given vertical line D, and the union of two trapezoidal maps computed in two vertical slabs of the plane that are adjacent through a vertical line D. The data structure we use is a modified Influence Graph, still allowing dynamic insertions and deletions of line segments in the map. The algorithms for both operations run in O(s(D) log n + log(2) n) time, where n is the number of line segments in the map, and so is the number of line segments intersected by D. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： dynamic algorithms randomized algorithms data structures parallel data structures trapezoidal map

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time counting and sampling of two-rowed contingency tables

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期246卷 265-278页

作者： Dyer, M Greenhill, C Univ Leeds Sch Comp Studies Leeds LS2 9JT W Yorkshire England

In this paper a Markov chain for contingency tables with two rows is defined. The chain is shown to be rapidly mixing using the path coupling method. We prove an upper bound for the mixing time of the chain. The upper bound is quadratic in the number of columns and linear in the logarithm of the table sum. By considering a specific problem, we prove a lower bound for the mixing time of the chain. The lower bound is quadratic in the number of columns and linear in the logarithm of the number of columns. A fully polynomial randomised approximation scheme for this problem is described. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： randomized algorithms contigency tables Markov chains complexity path coupling

来源：评论

学校读者我要写书评

暂无评论

Parallel complexity of computations with general and Toeplitz-like matrices filled with integers and extensions

引用

SIAM JOURNAL ON COMPUTING 2000年第4期30卷 1080-1125页

作者： Pan, VY CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

Computations with Toeplitz and Toeplitz-like matrices are fundamental for many areas of algebraic and numerical computing. The list of computational problems reducible to Toeplitz and Toeplitz-like computations includes, in particular, the evaluation of the greatest common divisor (gcd), the least common multiple (lcm), and the resultant of two polynomials, computing Pade approximation and the Berlekamp-Massey recurrence coefficients, as well as numerous problems reducible to these. Transition to Toeplitz and Toeplitz-like computations is currently the basis for the design of the parallel randomized NC (RNC) algorithms for these computational problems. Our main result is in constructing nearly optimal randomized parallel algorithms for Toeplitz and Toeplitz-like computations and, consequently, for numerous related computational problems ( including the computational problems listed above), where all the input values are integers and all the output values are computed exactly. This includes randomized parallel algorithms for computing the rank, the determinant, and a basis for the null-space of an n x n Toeplitz or Toeplitz-like matrix A filled with integers, as well as a solution x to a linear system A x = f if the system is consistent. Our algorithms use O ((log n) log(n log \\A\\)) parallel time and O (n log n) processors, each capable of performing (in unit time) an arithmetic operation, a comparision, or a rounding of a rational nu ber to a closest integer. The cost bounds cover the cost of the veri cation of the correctness of the output. The computations by these algorithms can be performed with the precision of O (n log \\A\\) bits, which matches the precision required in order to represent the output, except for the rank computation, where the precision of the computation decreases. The algorithms involve either a single random parameter or at most 2n - 1 parameters. The cited processor bounds are less by roughly factor n than ones supported by the known alg

关键词： parallel algorithms randomized algorithms Toeplitz matrix computations Toeplitz-like matrices polynomial gcd displacement rank computational complexity block Gauss-Jordan decomposition p-adic lifting Newton-Hensel's lifting

来源：评论

学校读者我要写书评

暂无评论

Trackless online algorithms for the server problem

引用

INFORMATION PROCESSING LETTERS 2000年第1-2期74卷 73-79页

作者： Bein, WW Larmore, LL Univ Nevada Dept Comp Sci Las Vegas NV 89154 USA

A class of "simple" online algorithms for the k-server problem is identified. This class, for which the term trackless is introduced, includes many known server algorithms. The k-server conjecture fails for trackless algorithms. A lower bound of 23/11 on the competitiveness of any deterministic trackless 2-server algorithm and a lower bound of 1 + root 2/2 on the competitiveness of any randomized trackless 2-server problem are given. (C) 2000 Published by Elsevier Science B.V. An rights reserved.

关键词： design of algorithms online algorithms randomized algorithms competitive analysis k-server problem paging

来源：评论

学校读者我要写书评

暂无评论

Reporting curve segment intersections using restricted predicates

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第4期16卷 245-256页

作者： Chan, TM Univ Waterloo Dept Comp Sci Waterloo ON N2L 3G1 Canada

We investigate how to report all k intersecting pairs among a collection of n x-monotone curve segments in the plane, using only predicates of the following forms: is an endpoint to the left of another? is an endpoint above a segment? do two segments intersect? By studying the intersection problem in an abstract setting that assumes the availability of certain "detection oracles", we obtain a near-optimal randomized algorithm that runs in O(n logn + n root k log(n(2)/k)) expected time. In the bichromatic case (where segments are colored red or blue with no red/red or blue/blue intersections), we find a better algorithm that runs in O((n + k) log(2+k/n) n) worst-case time, by modifying a known segment-tree method. Two questions of Boissonnat and Snoeyink are thus answered to within logarithmic factors, (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： segment intersection low-degree primitives randomized algorithms segment trees robust computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：