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

A scaling algorithm for multicommodity flow problems

OPERATIONS RESEARCH 1998年第2期46卷 231-246页

作者： Schneur, RR Orlin, JB PTCG Inc Burlington MA USA MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sending flow around negative cost cycles. Two parameters control the algorithm's behavior: the penalty parameter and the scaling parameter. In the epsilon-scaling phase, where epsilon is a function of the penalty and scaling parameters, the algorithm determines an E-optimal solution;a solution in which complementary slackness conditions are satisfied to within epsilon. We analyze the performance of the algorithm from both the theoretical and practical perspectives. The computational results support the theoretical behavior of the algorithm. They also demonstrate the efficiency of the algorithm for solving problem instances of different structure and size.

关键词： Networks/graphs multicommodity new algorithm for problem solving analysis of algorithm computational and theoretical analysis of a scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamical simulation of planar systems with changing contacts using configuration spaces

引用

JOURNAL OF MECHANICAL DESIGN 1998年第2期120卷 181-187页

作者： Sacks, E Joskowicz, L Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

This paper presents a contact analysis algorithm for pairs of rigid, curved planar parts based on configuration space computation. The algorithm is part of a dynamical simulator for planar systems with changing contact topologies. The configuration space of a pair of parts is a data structure that encodes the contact configurations for all pairs of part features. The configuration spaces of the interacting pairs in the mechanical system are constructed before the simulation. At each time step, the simulator queries the configuration spaces for contact changes instead of performing collision detection. The simulator demonstrates the efficacy of the configuration space approach to contact analysis. It achieves real-time performance on systems with complex contact geometry, curved parts, and changing contacts.

关键词： Mechanical systems configuration space CONTACT Pairing analysis of algorithm simulating simulator Contact Information contact configuration configurations Planar

来源：评论

学校读者我要写书评

暂无评论

AN algorithm FOR DETECTION OF MOVING OPTICAL TARGETS

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 1989年第1期25卷 56-63页

作者： POHLIG, SC Lincoln Laboratory M.I.T. Lexington MA USA

An algorithm is described for detecting moving optical targets against spatially nonstationary Poisson background and noise. The algorithm has applications in optical detection of objects such as meteors, asteroids, and satellites against a stellar background. A maximum-likelihood approach is used which results in reducing interference from stars. It is shown that by choosing a detection threshold to provide a constant false alarm rate, the resulting algorithm is independent of the signal strength of the target. An analysis of this algorithm is presented, showing the probability of detection for several false-alarm rates.

关键词： False alarms Moving Optical detection optical algorithms false alarm probability Object detection detection limit analysis of algorithm constant false alarm rate Signal Intensity satellites

来源：评论

学校读者我要写书评

暂无评论

k-Partitioning problems with partition matroid constraint

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期374卷 41-48页

作者： Wu, Biao Yao, Enyue Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

In this paper, we consider the k-partitioning problems with partition matroid constraint and present an algorithm called the layered LPT algorithm. With the objective of minimizing the maximum load, we show that the layered LPT algorithm has a tight worst case ratio of 2 - 1/m. With the objective of maximizing the minimum load, we show that the layered LPT algorithm has a tight worst case ratio of 1/m for the general case and, with certain conditions, the worst ratio can be improved to m/(2m - 1) for the general k case and to (m - 1) / (2m - 3) for the k = 3 case. (C) 2006 Elsevier B.V. All rights reserved.

关键词： partitioning constrained partition analysis of algorithm worst case ratio

来源：评论

学校读者我要写书评

暂无评论

AREA AND PERIMETER COMPUTATION OF THE UNION OF A SET OF ISO-RECTANGLES IN PARALLEL

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1995年第2期27卷 107-117页

作者： KANKANHALLI, MS FRANKLIN, WR RENSSELAER POLYTECH INST DEPT ELECT COMP & SYST ENGN TROY NY 12180 USA RENSSELAER POLYTECH INST DEPT COMP SCI TROY NY 12180 USA

Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results. (C) 1995 Academic Press, Inc

关键词： Medial axis transform Geometric-properties algorithms parallel random access machine model SIMD architecture Parallel algorithms algorithms analysis of algorithm vertex head medial axis perimeter Parallel Lines Optimization algorithms Connection Machine Rectangle

来源：评论

学校读者我要写书评

暂无评论

k-partitioning problems for maximizing the minimum load

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2003年第10-11期46卷 1671-1681页

作者： He, Y Tan, ZY Zhu, J Yao, EY Zhejiang Univ Dept Math State Key Lab CAD Hangzhou 310027 Peoples R China Zhejiang Univ CG Hangzhou 310027 Peoples R China Zhejiang Univ Coll Elect Engn Hangzhou 310027 Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Peoples 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{l/k, 1/([Sigma(i=1)(m) 1/i] + 1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2([Sigma(i=1)(m) 1/i] + 1). We further show that HARMONIC1 is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general k(i)-PARTITIONING problem. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： partitioning scheduling analysis of algorithm worst case ratio

来源：评论

学校读者我要写书评

暂无评论

Phase-shift calibration algorithm for phase-shifting interferometry

引用

JOURNAL OF THE OPTICAL SOCIETY OF AMERICA A-OPTICS IMAGE SCIENCE AND VISION 2000年第11期17卷 2061-2066页

作者： Chen, X Gramaglia, M Yeazell, JA Penn State Univ Dept Phys University Pk PA 16802 USA

We propose a novel phase-shift calibration algorithm. With this technique we determine the unknown phase shift, between two interferograms by examining the sums and differences of the intensities on each interferogram at the same spatial location, i.e., I-1(x, y) +/- I-2(x, y) These intensities are normalized so that they become sinusoidal in form. A uniformly illuminated region of the interferograms that contains at least a 2 pi variation in phase is examined. The extrema of these sums and differences are found in this region and are used to find the unknown phase shift. An error analysis of the algorithm is provided. In addition, an error-correction algorithm is implemented. The method is tested by numerical simulation and implemented experimentally. The numerical tests, including digitization error, indicate that the phase step has a root-mean-square (RMS) phase error of less than 10(-6) deg. Even in the presence of added intensity noise (5% amplitude) the RMS error does not exceed 1 deg. The accuracy of the technique is not sensitive to nonlinearity in the interferogram. (C) 2000 Optical Society of America [S0740-3232(00)01711-7].

关键词： extremum values Phase shift algorithms phase step ROOT-MEAN-SQUARE ERRORS sums interferometry analysis of algorithm Sinusoidal interference pattern Technology Root mean square

来源：评论

学校读者我要写书评

暂无评论

Randomized local elections

引用

INFORMATION PROCESSING LETTERS 2002年第6期82卷 313-320页

作者： Métivier, Y Saheb, N Zemmari, A Univ Bordeaux 1 ENSEIRB LaBRI F-33405 Talence France

关键词： analysis of algorithm graph performance analysis local election randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The Rys quadrature revisited: A novel formulation for the efficient computation of electron repulsion integrals over Gaussian functions

引用

JOURNAL OF CHEMICAL PHYSICS 2001年第5期114卷 2067-2078页

作者： Dupuis, M Marquez, A Pacific NW Natl Lab Environm Mol Sci Lab K8-91POB 999Battelle Blvd Richland WA 99352 USA Univ Seville Dept Chem Seville Spain

A novel formulation of the Rys quadrature algorithm for the calculation of the electron repulsion integrals over Gaussian basis functions is presented. The new algorithm is specifically designed for high contractions. As for the original Rys quadrature algorithm, the new algorithm is very efficient for high angular momentum functions. In addition it is also equally efficient for low angular momentum functions. The new algorithm takes unique advantage of (1) the numerical Rys quadrature methodology in (2) dealing with charge distributions a la McMurchie-Davidson and in (3) scaling integral blocks as a means of transferring angular momentum a la Gill-Head-Gordon-Pople. An analysis of the algorithm suggests very favorable floating-point operation counts. (C) 2001 American Institute of Physics.

关键词： floating point arithmetic QUADRATURE algorithms Gauss analysis of algorithm basis functions Integral equations Repulsion

来源：评论

学校读者我要写书评

暂无评论

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

引用

INFORMATION AND COMPUTATION 2005年第1期196卷 57-70页

作者： Tan, ZY He, Y Epstein, L Interdisciplinary Ctr Sch Comp Sci IL-46150 Herzliyya Israel Zhejiang Univ State Key Lab CAD & CG Dept Math Hangzhou 310027 Peoples R China

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l(p) norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s greater than or equal to 1. For minimizing the lp norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p. (C) 2004 Elsevier Inc. All rights reserved.

关键词： analysis of algorithm scheduling semi-online competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：