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

Two-Dimensional Voronoi Diagrams in the L_p-Metric

Journal of the ACM (JACM) 1980年第4期27卷 604-618页

作者： Lee, D.T. University of Illinois Urbana-Champaign Urbana Illinois United States Department of Electrical Engineering and Computer Science Northwestern University Evanston IL 60201 United States

The Voronoi diagram, also known as the Thiessen diagram, for a set of N points in the Cartesian plane in which the L,-metnc is the distance measure, where p is a real number between 1 and 0o inclusive, is defined, and an algorithm for constructing the dmgram m O(NlogN) tune is presented This algonthm uses the divide-and-conquer technique. Many proximity problems revolving a set of points, such as finding the nearest neighbor of a given point, finding the minimum spamung tree, findmg the smallest circle (m the Lp-metric) enclosing the point set, etc., can be solved very efficiently via the diagram The running time of the algorithm presented is also shown to be optimal to within a constant factor. © 1980, ACM. All rights reserved.

关键词： analysis of algorithm computational complexity computational geometry divide-and-conquer Lpmetric Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem

Phase transitions and complexity in computer science: an ove...

引用

21st IUPAP International Conference on Statistical Physics

作者： Biroli, G Cocco, S Monasson, R ENS CNRS Phys Theor Lab F-75005 Paris France Rutgers State Univ Dept Phys & Astron Ctr Mat Theory Piscataway NJ 08854 USA Univ Illinois Dept Phys Chicago IL 60607 USA Univ Chicago James Franck Inst Chicago IL 60637 USA

Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems, Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. (C) 2002 Published by Elsevier Science B.V.

关键词： statistical physics phase transitions optimization satisfiability analysis of algorithm

来源：评论

学校读者我要写书评

暂无评论

A modified branch-and-bound strategy

引用

Information Processing Letters 1973年第3期2卷 65-69页

作者： Tang, D.T. Wong, C.K. IBM Thomas J. Watson Research Center Yorktown Heights NY United States

来源：评论

学校读者我要写书评

暂无评论

Domain-Decomposition Technique for Efficient analysis of Rotationally Symmetric Reflector Systems Containing 3D Structures

Domain-Decomposition Technique for Efficient Analysis of Rot...

引用

European Conference on Antennas and Propagation

作者： Erik Jorgensen Peter Meincke TICRA Laederstraede 34 DK-1201 Copenhagen K Denmark

ISBN: (纸本)9781467321877

An efficient algorithm for analysis and optimization of rotationally symmetric reflector antennas, possibly including 3D support structures and/or waveguide components, is presented. The high efficiency is obtained by using a domain-decomposition approach where each region of space is characterized independently using a generalized admittance matrix description. The admittance matrices are obtained using circular mode-matching, higher-order 3D MoM, or a newly developed higher-order MoM for bodies of revolution (BoR-MoM). The antenna performance is rigorously evaluated by cascading the admittance matrices, which subsequently allows computation of surface currents or fields in all subdomains. The new algorithm allows fast and accurate analysis and optimization of rotationally symmetric reflectors, even in cases that would normally require a time-consuming 3D solution due to the lack of rotational symmetry.

关键词： admittance matrix analysis of algorithm reflectors Reflector antennas CENTROSYMMETRIC waveguide components antenna performance Three Dimensions Surface streams Rotational symmetry METHOD OF MOMENTS impedance efficient algorithm

来源：评论

学校读者我要写书评

暂无评论

analysis of Scalar Fields over Point Cloud Data 09

Analysis of Scalar Fields over Point Cloud Data

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Frederic Chazal Leonidas J. Guibas Steve Y. Oudot Primoz Skraba INRIA Geometrica group Department of Computer Science Stanford University

Given a real-valued function f defined over some metric space X, is it possible to recover some structural information about f from the sole information of its values at a finite set L {is contained in} X of sample points, whose pairwise distances in X are given? We provide a positive answer to this question. More precisely, taking advantage of recent advances on the front of stability for persistence diagrams, we introduce a novel algebraic construction, based on a pair of nested families of simplicial complexes built on top of the point cloud L, from which the persistence diagram of f can be faithfully approximated. We derive from this construction a series of algorithms for the analysis of scalar fields from point cloud data. These algorithms are simple and easy to implement, have reasonable complexities, and come with theoretical guarantees. To illustrate the generality of the approach, we present some experimental results obtained in various applications, ranging from clustering to sensor networks (see the electronic version of the paper for color pictures).

关键词： SCALAR FIELDS Clouds Scalar analysis of algorithm metric space Fields analysis algorithms Environmental persistence

来源：评论

学校读者我要写书评

暂无评论

Many-Core Graph Workload analysis 18

Many-Core Graph Workload Analysis

引用

ACM/IEEE International Conference for High Performance Computing, Networking, Storage, and analysis

作者： Stijn Eyerman Wim Heirman Kristof Du Bois Joshua B. Fryman Ibrahim Hur Intel Corporation Kontich Belgium Intel Corporation

ISBN: (纸本)9781538683859

Graph applications have specific characteristics that are not common in other application domains and therefore require thorough analysis to guide future graph processing hardware design. In this paper, we analyze multiple graph applications on current multi and many-core processors, and provide conclusions and recommendations for future designs. We restate well-known characteristics of graph applications, such as a low compute to memory ratio and irregular memory access patterns, but we also provide new important insights on executing graph applications on many-core processors. Our main novel observations are (i) some memory streams do show locality, while others show no locality, (ii) thread imbalance becomes a major problem with many threads, and (iii) many threads are required to saturate high-bandwidth memories. The first observation calls for a selective memory access policy, where accesses with locality are cached and prefetched, while accesses without locality can remain uncached to save cache capacity, and can fetch only one element from memory instead of a full cache line to save on memory bandwidth. The last two observations are contradicting: more threads are needed, but they are not used efficiently due to thread imbalance. Our recommendation is therefore to thoroughly revise the graph analysis algorithms to provide more scalable parallelism to be able to exploit the potential of many-core architectures with high-bandwidth memory. In addition, providing a few high-performance cores can speed up sections with low parallelism.

关键词： Instruction sets Benchmark testing Hardware Parallel processing Bandwidth Multicore processing instruction sets Benchmark testing PARALLEL PROCESSING (COMPUTERS) Computer hardware Bandwidth Memory THREADS Line graph Memory high-bandwidth analysis of algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for semi on-line multiprocessor scheduling problems

引用

Journal of Zhejiang University-Science A(Applied Physics & Engineering) 2002年第1期 61-65页

作者：何勇杨启帆谈之奕姚恩瑜

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

κ-Partitioning problems for maximizing the minimum load

引用

Computers & Mathematics with Applications 2003年第1-11期46卷 1671-1681页

作者： Yong He Zhiyi Tan Jing Zhu Enyu Yao Department of Mathematics Zhejiang University State Key Lab of CAD and CG Zhejiang University Hangzhou 310027 P.R. China College of Electrical Engineering Zhejiang University Hangzhou 310027 P.R. China Department of Mathematics Zhejiang University Hangzhou 310027 P.R. China

The optimization versions of the k -PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/ k ,1/ m }. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/ k , 1/(⌈ Σ i =1 m 1/ i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σ i =1 m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κ i -PARTITIONING problem.

关键词： Partitioning Scheduling analysis of algorithm Worst case ratio

来源：评论

学校读者我要写书评

暂无评论

DETERMINING THE MODE IN PARALLEL

引用

Parallel Processing Letters 1991年第1期1卷 3-10页

作者： ELIEZER A. ALBACEA Department of Computer Science Australian National University GPO Box 4 Canberra ACT 2601 Australia

We show that the problem of finding the element with the highest frequency in a set, the mode of the set, is bounded by the problem of sorting multisets. As a consequence, we obtained an improvement of the upper bound for finding the mode. This result was obtained by presenting an algorithm that requires linear time when the set is initially sorted. The same algorithm was parallelized to produce the first optimal parallel algorithm for finding the mode.

关键词： Mode analysis of algorithm parallel algorithm optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：