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

randomized routing, selection, and sorting on the OTIS-mesh

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第9期9卷 833-840页

作者： Rajasekaran, S Sahni, S Univ Florida Dept Comp Sci & Informat Engn Gainesville FL 32611 USA

The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. in this paper we present efficient algorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N-2-processor OTIS-Mesh is 4 root N - 3. We present an algorithm for routing any partial permutation in 4 root N + o(root N) time. Our selection algorithm runs in time 6 root N + o(root N) and our sorting algorithm runs in 8 root N + o(root N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.

关键词： optical computing mesh-connected computers parallel algorithms sorting packet routing selection randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized naming using wait-free shared variables

引用

DISTRIBUTED COMPUTING 1998年第3期11卷 113-124页

作者： Panconesi, A Papatriantafilou, M Tsigas, P Vitanyi, P Aarhus Univ Dept Comp Sci BRICS DK-8000 Aarhus C Denmark Chalmers Univ Technol Dept Comp Sci S-41296 Gothenburg Sweden CWI NL-1098 SJ Amsterdam Netherlands

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For n processes and is an element of > 0, the protocol uses a name space of size (1 + is an element of)n and O(n log n log log n) running time (read/writes to shared bits) with probability at least 1-o(1), and O(n log(2) n) overall expected running time. The protocol is based on the wait-free implementation of a novel alpha-Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least alpha in the face of the strongest possible adaptive adversary.

关键词： naming problem symmetry breaking unique process ID asynchronous distributed protocols fault-tolerance shared memory wait-free read/write registers atomicity test-and-set objects randomized algorithms adaptive adversary

来源：评论

学校读者我要写书评

暂无评论

A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions

引用

MATHEMATICAL AND COMPUTER MODELLING 1998年第1期27卷 75-99页

作者： Deshpande, AS Triantaphyllou, E Louisiana State Univ Dept Ind & Mfg Syst Engn Baton Rouge LA 70803 USA

Two new heuristics are presented for inferring a small size Boolean function from complete and incomplete examples in polynomial time. These examples are vectors defined in {1, 0}(n) for the complete case, or in {1,0, *}(n) for the incomplete case (where n is the number of binary attributes or atoms and "*" indicates unknown value). Each example is either positive or negative, if it must be accepted or rejected by the target function, respectively. For the incomplete case, however, some examples may be unclassifiable. Moreover, computational results indicate that the proposed heuristics may also be effective in solving very large problems with thousands of examples.

关键词： Boolean functions CNF/DNF form Learning from examples Logical analysis clause satisfiability problem GRASP randomized algorithms inductive inference

来源：评论

学校读者我要写书评

暂无评论

Bounding the power of preemption in randomized scheduling

引用

SIAM JOURNAL ON COMPUTING 1998年第4期27卷 993-1015页

作者： Canetti, R Irani, S IBM Corp Div Res TJ Watson Res Ctr Yorktown Hts NY 10598 USA Univ Calif Irvine Dept Informat & Comp Sci Irvine CA 92717 USA

We study on-line scheduling in overloaded systems. Requests for jobs arrive one by one as time proceeds;the serving agents have limited capacity and not all requests can be served. Still, we want to serve the "best" set of requests according to some criterion. In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios. We show that, surprisingly, in many other scenarios this is not the case. In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. Our bound applies to several recently studied problems. In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms.

关键词： randomized algorithms scheduling preemption lower bounds

来源：评论

学校读者我要写书评

暂无评论

Implementation of the simultaneous perturbation algorithm for stochastic optimization

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 1998年第3期34卷 817-823页

作者： Spall, JC Johns Hopkins Univ Appl Phys Lab Laurel MD 20723 USA

The need for solving multivariate optimization problems is pervasive in engineering and the physical and social sciences. The simultaneous perturbation stochastic approximation (SPSA) algorithm has recently attracted considerable attention for challenging optimization problems where it is difficult or impossible to directly obtain a gradient of the objective function with respect to the parameters being optimized. SPSA is based on an easily implemented and highly efficient gradient approximation that relies on measurements of the objective function, not on measurements of the gradient of the objective function. The gradient approximation is based on only two function measurements (regardless of the dimension of the gradient vector). This contrasts with standard finite-difference approaches, which require a number of function measurements proportional to the dimension of the gradient vector. This paper presents a simple step-by-step guide to implementation of SPSA in generic optimization problems and offers some practical suggestions for choosing certain algorithm coefficients.

关键词： approximation theory iterative methods mathematics computing optimisation perturbation techniques randomised algorithms stochastic processes MATLAB code algorithm coefficients efficient gradient approximation gain sequences generic optimization problems dimensions randomized algorithms Stochastic Processes Approximation Theory iterative methods Markov chain Objective function perturbation techniques Gradient vector

来源：评论

学校读者我要写书评

暂无评论

Probabilistic enhancement of classical robustness margins: The unirectangularity concept

引用

SYSTEMS & CONTROL LETTERS 1998年第1期35卷 31-43页

作者： Lagoa, CM Shcherbakov, PS Barmish, BR Univ Wisconsin ECE Dept Madison WI 53706 USA Moscow Inst Control Sci Moscow Russia

The focal point of this paper is a control system subjected to parametric uncertainty. Motivated by the newly emerging theory of probabilistic robustness, the risk of performance violation is assessed with uncertainty bounds which exceed classical deterministic margins. For a wide class of problems, the Uniformity Principle (UP) developed by Barmish and Lagoa (Math. Control Signals Systems 10 (1997) 203-222), makes it possible to estimate the probability of performance satisfaction with almost no a priori statistical information about the uncertainty. The application of the UP is, however, limited to problems satisfying certain convexity and symmetricity conditions. Since such conditions are violated in many practical problems, the objective in this paper is to extend the application of the UP. To this end, by working with a so-called unirectangularity condition, a procedure is implemented for computing probabilities of performance and the associated improvements of deterministic robustness margins. That is, given any robustness radius ro which is computable via deterministic methods, a probabilistic enhancement of this margin R(0)(epsilon)greater than or equal to r(0) with pre-specified level of risk epsilon>0 is provided. The radius R(0)(epsilon) is called a risk-adjusted robustness margin. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

关键词： randomized algorithms Monte Carlo analysis robustness analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for geometric optimization

引用

ACM COMPUTING SURVEYS 1998年第4期30卷 412-458页

作者： Agarwal, PK Sharir, M Duke Univ Dept Comp Sci Ctr Geometr Comp Durham NC 27708 USA Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel NYU Courant Inst Math Sci New York NY 10012 USA

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, prune-and-search techniques for linear programming and related problems, and LP-type problems and their efficient solution. We then describe a wide range of applications of these and other techniques to numerous problems in geometric optimization, including facility location, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other query-type problems.

关键词： clustering collision detection linear programming matrix searching parametric searching proximity problems prune-and-search randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight bounds on parallel list marking

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1998年第2期51卷 75-88页

作者： Bhatt, SN Bilardi, G Herley, KT Pucci, G Ranade, A Bell Commun Res Inc Morristown NJ 07960 USA Univ Padua Dipartimento Elettron & Informat I-35131 Padua Italy Univ Illinois Dept Elect Engn & Comp Sci Chicago IL 60607 USA Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Ireland Indian Inst Technol Dept Comp Sci & Engn Bombay 400076 Maharashtra India

The list marking problem involves marking the nodes of an L-node linked list stored in the memory of a (p, n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish an Omega(min{l, n/p}) randomized lower bound for l-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tight Theta(min {l, l/p + root(n/p) log n }) bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values. (C) 1998 Academic Press.

关键词： list marking list ranking linked structures shared-memory machines parallel algorithms randomized algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Approximate graph coloring by semidefinite programming

引用

JOURNAL OF THE ACM 1998年第2期45卷 246-265页

作者： Karger, D Motwani, R Sudan, M MIT Comp Sci Lab Cambridge MA 02139 USA Stanford Univ Stanford CA 94305 USA

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with min {O(Delta(1/3) log(1/2) Delta log n), O(n(1/4) log(1/2) n)} colors where Delta is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first nontrivial approximation result as a function of the maximum degree Delta. This result can be generalized to k-colorable graphs to obtain a coloring using min {O(Delta(1-2/k) log(1/2) Delta log n), O(n(1-3/(k+1)) log(1/2) n)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz theta-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number;by duality this also demonstrates interesting new facts about the theta-function.

关键词： approximation algorithms chromatic number graph coloring NP-completeness randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Routing on networks of optical crossbars

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期196卷 181-200页

作者： auf der Heide, FM Schroder, K Schwarze, F Univ Gesamthsch Paderborn Heinz Nixdorf Inst D-33095 Paderborn Germany Univ Gesamthsch Paderborn Dept Math & Comp Sci D-33095 Paderborn Germany

We describe routing algorithms on networks composed of optical busses. Using networks with short busses and small degree we are able to give very fast routing algorithms. First, we describe a leveled optical network and a routing algorithm for it. Next, we show how to simulate this network on high-dimensional meshes of optical busses (MOBs). We present algorithms for routing, e.g., h-relations with runtime being linear in h, doubly logarithmic in size and polynomial in the dimension of the mesh. Previous results are exponential in the dimension. E.g., routing an h-relation on a d-dimensional MOB of size N requires O(d(5) log d log log N + d(3)h) steps, with high probability. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： parallel algorithms randomized algorithms optical networks adaptive routing multibutterflies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：