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

AN OPTIMAL CONVEX-HULL ALGORITHM IN ANY FIXED DIMENSION

DISCRETE & COMPUTATIONAL GEOMETRY 1993年第4期10卷 377-409页

作者： CHAZELLE, B Princeton University

We present a deterministic algorithm for computing the convex hull of n points in E(d) in optimal O(n log n + n right perpendicular d/2 left perpendicular) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram of n points in d-space in optimal O(n log n + n inverted right perpendicular d/2 inverted left perpendicular) time.

关键词： convex hull deterministic algorithms Voronoi diagrams Fixed algorithms dimensions assembling measurement Time optimal

来源：评论

学校读者我要写书评

暂无评论

SPECIAL SECTION ON THE FORTY-FIFTH ANNUAL ACM SYMPOSIUM ON THE THEORY OF COMPUTING (STOC 2013)

引用

SIAM JOURNAL ON COMPUTING 2016年第2期45卷 459-460页

作者： Aspnes, James Ishai, Yuval Miltersen, Peter Bro

This issue of SICOMP contains seven specially selected papers from STOC 2013, the Forty-Fifth Annual ACM Symposium on the Theory of Computing, which was held June 1 through 4, 2013, in Palo Alto, California. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough the reviewing process of SICOMP. The program committee for STOC 2013 consisted of an executive committee made up of Boaz Barak, Irit Dinur, Leslie Goldberg, Giuseppe F. Italiano, Sampath Kannan, Neeraj Kayal, Michael Mitzenmacher, and Miklos Santha, supervising a broader program committee made up of Scott Aaronson, Susanne Albers, Benny Applebaum, James Aspnes, Per Austrin, Avrim Blum, Anne Broadbent, Peter Bürgisser, John Byers, Amit Chakrabarti, Shuchi Chawla, Bernard Chazelle, Xi Chen, Julia Chuzhoy, Graham Cormode, Artur Czumaj, Constantinos Daskalakis, Zeev Dvir, Jeff Erickson, Lance Fortnow, Craig Gentry, Anna Gilbert, Sudipto Guha, Mohammed Taghi Hajiaghayi, Moritz Hardt, Avinatan Hassidim, Monika Henzinger, Maurice Herlihy, Nicole Immorlica, Russell Impagliazzo, Piotr Indyk, Yuval Ishai, Mark Jerrum, Yael Kalai, Tali Kaufman, Haim Kaplan, Jonathan Kelner, Valerie King, Samir Khuller, Robert Kleinberg, Elias Koutsoupias, Robert Krauthgamer, Pinyan Lu, Aleksander Madry, Dániel Marx, Peter Bro Miltersen, Moni Naor, Ilan Newman, Rina Panigrahy, Prasad Raghavendra, Andrea Richa, Michael Schapira, Rocco Servedio, Amir Shpilka, Cliff Stein, David Steurer, Mikkel Thorup, Virginia Vassilevska Williams, Eric Vigoda, Ryan Williams, Ronald de Wolf, and David Zuckerman. The program chair was Joan Feigenbaum. Included in this issue are the following papers: ``An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube," by Deeparnab Chakrabarty and C. Seshadhri, provides a randomized tester for near-monotone functions requiring sublinear queries. ``Answering $n^{2+o(1)}$ Coun

关键词： deterministic algorithms Boolean functions (Mathematics) Randomization (Statistics)

来源：评论

学校读者我要写书评

暂无评论

Uniform deterministic Dictionaries

引用

ACM TRANSACTIONS ON algorithms 2008年第1期4卷 1-1页

作者： Ruzic, Milan IT Univ Copenhagen Computat Log & Algorithms Grp DK-2300 Copenhagen Denmark

We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting "good" hash functions. The main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. The model of computation is the Word RAM, and it is assumed that the machine word-size matches the size of keys in bits. Many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at "compile time" for the stated time bounds to hold. The currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. In contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. Our family of dynamic dictionaries achieves a performance of the following type: lookups in time O(t) and updates in amortized time O(n(1/t)), for an appropriate parameter function t. Update procedures require division, whereas searching uses multiplication only.

关键词： deterministic algorithms perfect hashing

来源：评论

学校读者我要写书评

暂无评论

Making deterministic Signatures Quickly

引用

ACM TRANSACTIONS ON algorithms 2009年第3期5卷 26-1-26-26页

作者： Ruzic, Milan IT Univ Copenhagen DK-2300 Copenhagen Denmark

We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the practical RAM, and the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time of O(log log n) and construction time of O(n) on sorted input on a word RAM, and a static predecessor structure for variable-and unbounded length binary strings that in the cache-oblivious model has a query performance of O(vertical bar s vertical bar/B + log vertical bar s vertical bar) I/Os, for query argument s.

关键词： deterministic algorithms perfect hashing

来源：评论

学校读者我要写书评

暂无评论

Ant-Algorithm-Annealing-Algorithm-based Optimization Approach for MCM Interconnect Test

Ant-Algorithm-Annealing-Algorithm-based Optimization Approac...

引用

13th International Conference on Electronic Packaging Technology and High Density Packaging (ICEPT-HDP)

作者： Lei, Chen Guilin Univ Elect Technol Guilin 541004 Guangxi Peoples R China

ISBN: (纸本)9781467316811

A novel optimization approach based on ant algorithm (AA) and simulated annealing algorithm (SA) is presented for the Multi-chip Module (MCM) interconnect test generation problem in this paper. In order to apply ant algorithm into the interconnect test, the pheromone updating rule and state transition rule is designed by combing the characteristics of MCM interconnect test generation. By using the method, the ideal searching direction of global optimal solution could be found as soon as possible, while the shortcomings of high initial temperature required and slow convergence speed of simulated annealing algorithm were also overcame. AA generates the initial candidate test vectors in this approach. In order to get the best test vector with the high fault coverage, SA is employed to evolve the candidates generated by AA. The international standard MCM benchmark circuit was used to verify the approach. Comparing with not only the evolutionary algorithms, but also the deterministic algorithms, simulation results indicate that this optimization approach can achieve high fault coverage, compact test set and short execution time.

关键词： ant colony optimisation convergence deterministic algorithms evolutionary computation integrated circuit interconnections multichip modules simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Solving the at-most-once problem with nearly optimal effectiveness

引用

THEORETICAL COMPUTER SCIENCE 2013年 496卷 69-88页

作者： Kentros, Sotirios Kiayias, Aggelos Univ Connecticut Storrs CT USA Univ Athens Athens Greece

We present and analyze a wait-free deterministic algorithm for solving the at-most-once problem: how m shared-memory fail-prone processes perform asynchronously n jobs at most once. Our algorithmic strategy provides for the First time nearly optimal effectiveness, which is a measure that expresses the total number of jobs completed in the worst case. The effectiveness of our algorithm equals n - 2m + 2. This is up to an additive factor of m close to the known effectiveness upper bound n - m + 1 over all possible algorithms and improves on the previously best known deterministic solutions that have effectiveness only n - log m.o(n). We also present an iterative version of our algorithm that for any m = O((3+epsilon)root n/log n) is both effectiveness-optimal and work-optimal, for any constant epsilon > 0. We then employ this algorithm to provide a new algorithmic solution for the Write-All problem which is work optimal for any m = O((3+epsilon)root n/log n). (C) 2013 Elsevier B.V. All rights reserved.

关键词： At-most-once problem Task allocation Write-all I/O automata Asynchronous shared memory deterministic algorithms Distributed computing

来源：评论

学校读者我要写书评

暂无评论

An object-oriented optimization library for finite element method software

引用

IEEE TRANSACTIONS ON MAGNETICS 2000年第4期36卷 1057-1060页

作者： Costa, MC Coulomb, JL Maréchal, Y Univ Grenoble 1 Lab Electrotech Grenoble LEG ENSIEGINPGCNRS UMR 5529 F-38402 St Martin Dheres France

This paper presents a structure of classes based on Object-Oriented Programming, which allows the development of an Optimization Library, In this library, deterministic and stochastic optimization algorithms are considered, as well as algorithms that work with constrained or unconstrained objective functions. First of all,,we will present the characteristics of some main optimization methods used in the last years, mainly in the electromagnetic area. Later on, based on these characteristics, we will show the classes created for the implementation of this optimization library. Finally, we will present the communication architecture used for data exchange between this library and a Finite Element Method software.

关键词： deterministic algorithms object oriented programming optimization methods stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

Two-stage algorithm for efficient transmission expansion planning with renewable energy resources

引用

IET RENEWABLE POWER GENERATION 2017年第3期11卷 320-329页

作者： Majumder, Subir Shereef, R. M. Khaparde, Shrikrishna A. Indian Inst Technol Dept Energy Sci & Engn Bombay Maharashtra India Coll Engn Trivandrum Dept Elect Engn Trivandrum Kerala India Indian Inst Technol Dept Elect Engn Bombay Maharashtra India

In this study, a 'two-stage' deterministic algorithm an for efficient transmission expansion planning with renewable energy ( RE) resources under the assumption that existing conventional generators provide the reserve to mitigate RE generation forecast error has been proposed. Zero-RE penetration has been considered as a 'reference scenario', as well as cost-minimisation objective has been considered as a planning criterion in Stage 1. In the proposed algorithm, Stage 2 is required to be solved only if the network performance degrades in relation to the reference scenario. In Stage 2, congestion cost is also incorporated as a sub-objective. Here, the locational marginal prices of the unit scheduling problem obtained from the solution of Stage 1 have been used to calculate the congestion cost. In addition to being computationally tractable, the proposed algorithm guarantees performance improvement in the network. The planning horizon is divided into smaller blocks to facilitate delayed investment. When implemented on an IEEE 24-bus reliability test system, the proposed algorithm generated minimum cost plan with better performance.

关键词： power transmission planning renewable energy sources deterministic algorithms minimisation power generation scheduling power transmission reliability investment efficient transmission expansion planning renewable energy resources two-stage deterministic algorithm RE generation forecast error mitigation zero-RE penetration reference scenario cost-minimisation objective network performance congestion cost locational marginal prices unit scheduling problem planning horizon delayed investment IEEE 24-bus reliability test system

来源：评论

学校读者我要写书评

暂无评论

A Simulation-Based Approach for Control Design of Uncertain UAVs

A Simulation-Based Approach for Control Design of Uncertain ...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Capello, Elisa Tempo, Roberto Politecn Torino Dept Mech & Aerosp Engn Corso Duca Abruzzi 24 I-10129 Turin Italy Politecn Torino CNR IEIIT I-10129 Turin Italy

ISBN: (纸本)9781467320665

The objective of this paper is the development of a randomized Linear Quadratic Regulator (LQR) algorithm via gradient-based methods for Unmanned Aerial Vehicles (UAVs) subject to uncertainty to cope with different operating conditions. A controller gain is synthesized using a Lyapunov approach dealing with a formation of two mini-UAV systems in the classical Leader/Wingman configuration. The advantages of the proposed technique over the existing deterministic methods for control design are as follows: (i) the uncertainty structure is not defined a priori and (ii) one Lyapunov inequality is approximately solved at each iteration of the algorithm, so that the number of inequalities does not grow with the number of uncertain parameters. The main contribution of this paper is to demonstrate that the proposed sequential algorithm provides a randomized controller which stabilizes the uncertain system. This probabilistic technique is then validated with an extensive a posteriori analysis. The final result is to show that the UAV reaches the desired altitude without an additional Proportional-Integral-Derivative (PID) channel, and therefore tuning of the controller gains is avoided.

关键词： Lyapunov methods approximation theory autonomous aerial vehicles control system synthesis deterministic algorithms gradient methods iterative methods linear quadratic control probability random processes randomised algorithms stability uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Analysis of Throughput-Constrained Tactical Wireless Networks 33

Analysis of Throughput-Constrained Tactical Wireless Network...

引用

33rd Annual IEEE Military Communications Conference on Affordable Mission Success - Meeting the Challenge (MILCOM)

作者： Nicholas, Paul J. Tkacheff, Jeffrey C. Kuhns, Chana M. US Marine Corps Operat Anal Div Quantico VA 22134 USA

ISBN: (纸本)9781479967704

Communications networks supporting tactical military operations are often constrained by satellite throughput capacities. Using network architecture information and a traffic flow model based on packet captures from a large field exercise, we formulate and solve a multicommodity maximum flow problem (MCMFP) to approximate communications traffic within a tactical wireless network. The model provides a deterministic method of quickly identifying and analyzing network bottlenecks and quantifying the value of additional network throughput. We use this model to examine the interplay between a logical traffic model and the physical architecture used to support it. We also present a method for optimizing the performance of a network by re-arranging existing wireless links. To our knowledge, we are the first to use an MCMFP to identify network bottlenecks within a U.S. Marine Corps tactical wireless network using a traffic model based on actual packet captures.

关键词： deterministic algorithms military communication optimisation packet radio networks radio links satellite communication telecommunication traffic MCMFP US marine corps tactical wireless network approximate communication traffic networks deterministic method large field exercise logical traffic flow model multicommodity maximum flow problem network bottlenecks packet captures performance optimization physical network architecture information satellite throughput capacity throughput-constrained tactical wireless networks analysis wireless links Linear programming Network topology Optimization Satellites Throughput Wide area networks Wireless communication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：