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

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

作者： Oliver Friedmann Thomas Dueholm Hansen Uri Zwick Department of Computer Science University of Munich Department of Computer Science Aarhus University

ISBN: (纸本)9780898719932

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matousek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i.e., 2~(O((n log n)~(1/2))), where n is the number of vertices in the game. We focus in this paper on the algorithm of Matousek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matousek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the 2~(O((n log n)~(1/2))) upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matousek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.

关键词： Game theory Runtime Articular Bone Surface algorithms family Game animals Upper bound Random Polynomial time AUTOMATA THEORY randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding the Most Probable String and the Consensus String: an Algorithmic Study 11

Finding the Most Probable String and the Consensus String: a...

引用

IWPT 2011

作者： Colin de la Higuera Jose Oncina Université de Nantes CNRS LINA France Universidad de Alicante Alicante Spain

ISBN: (纸本)9781932432046

The problem of finding the most probable string for a distribution generated by a weighted finite automaton or a probabilistic grammar is related to a number of important questions: computing the distance between two distributions or finding the best translation (the most probable one) given a probabilistic finite state transducer. The problem is undecidable with general weights and is NP-hard if the automaton is probabilistic. We give a pseudo-polynomial algorithm which computes the most probable string in time polynomial in the inverse of the probability of the most probable string itself, both for probabilistic finite automata and probabilistic context-free grammars. We also give a randomised algorithm solving the same problem.

关键词： Probability Cosmic strings Likely randomized algorithms context-free grammars finite state machines Automata Nondeterministic polynomial-time hard FINDINGS Inverse

来源：评论

学校读者我要写书评

暂无评论

Sequential randomized algorithms for Robust Optimization

Sequential Randomized Algorithms for Robust Optimization

引用

Proceedings of the 46th IEEE Conference on Decision and Control, Pages 5971-6447

作者： Takayuki Wada Yasumasa Fujisaki Graduate School of Science and Technology Kobe University Kobe Japan Graduate School of Engineering Kobe University Kobe Japan

ISBN: (纸本)9781424414970;1424414970

A probabilistic approach is considered for robust optimization, where a convex objective function is minimized subject to a parameter dependent convex constraint. A novel sequential randomized algorithm is proposed for solving this optimization employing the stochastic ellipsoid method. It is shown that the upper bounds of the numbers of random samples and updates of the algorithm are much less than those of the stochastic bisection method utilizing the stochastic ellipsoid method at each iteration. This feature actually leads to a computational advantage, which is demonstrated through a numerical example.

关键词： randomized algorithms Objective function random sample Ellipsoid Sequential Stochastic numerical example Upper bound Convexity

来源：评论

学校读者我要写书评

暂无评论

randomized Receding Horizon Navigation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2010年第11期55卷 2640-2644页

作者： Tanner, Herbert G. Piovesan, Jorge L. Univ Delaware Dept Mech Engn Newark DE 19716 USA Univ New Mexico K&A Wireless LLC Albuquerque NM 87112 USA

The note combines (weak) control Lyapunov function-based nonlinear receding horizon control, with randomized optimization. This approach is applied to the problem of robot navigation in the presence of state and input constraints. It is shown that under certain conditions, relaxing the definiteness requirements on the terminal cost function allows one to select control inputs through a Monte-Carlo optimization scheme in a way that preserves the stability and convergence properties of the closed loop system. While the particular randomized optimization scheme used here can be substituted for the nonlinear optimal control method of choice, the introduction of randomization in receding horizon optimization is anticipated to offer additional trade-offs between performance and computation speed compared to the fixed-overhead nonlinear optimal control strategies typically employed.

关键词： Model predictive control (MPC) randomized algorithms robot navigation

来源：评论

学校读者我要写书评

暂无评论

A randomized CUTTING PLANE METHOD WITH PROBABILISTIC GEOMETRIC CONVERGENCE

引用

SIAM JOURNAL ON OPTIMIZATION 2010年第6期20卷 3185-3207页

作者： Dabbene, F. Shcherbakov, P. S. Polyak, B. T. Politecn Torino IEIIT CNR I-10129 Turin Italy Russian Acad Sci Inst Control Sci Moscow Russia

We propose a randomized method for general convex optimization problems;namely, the minimization of a linear function over a convex body. The idea is to generate N random points inside the body, choose the best one, and cut the part of the body defined by the linear constraint. We analyze the convergence properties of the algorithm from a theoretical viewpoint, i.e., under the rather standard assumption that an algorithm for uniform generation of random points in the convex body is available. Under this assumption, the expected rate of convergence for such method is proved to be geometric. This analysis is based on new results on the statistical properties of the empirical minimum over a convex body that we obtained in this paper. Moreover, explicit sample size results on convergence are derived. In particular, we compute the minimum number of random points that should be generated at each step in order to guarantee that, in a probabilistic sense, the method performs better than the deterministic center-of-gravity algorithm. From a practical viewpoint, we show how the method can be implemented using hit-and-run versions of Markov-chain Monte Carlo algorithms and exemplify the performance of this implementable modification via a number of illustrative problems. A crucial notion for the hit-and-run implementation is that of boundary oracle, which is available for most optimization problems including linear matrix inequalities and many other kinds of constraints. Preliminary numerical results for semidefinite programs are presented confirming that the randomized approach might be competitive to modern deterministic convex optimization methods.

关键词： convex optimization randomized algorithms hit-and-run linear matrix inequalities

来源：评论

学校读者我要写书评

暂无评论

randomized anisotropic transform for nonlinear dimensionality reduction

引用

GEM-INTERNATIONAL JOURNAL ON GEOMATHEMATICS 2010年第1期1卷 23-50页

作者： Chui, Charles K. Wang, Jianzhong Stanford Univ Dept Stat Stanford CA 94305 USA Univ Missouri Dept Math & Comp Sci St Louis MO 63121 USA Sam Houston State Univ Dept Math & Stat Huntsville TX 77341 USA

An innovative method is introduced in this paper to significantly increase computational speed and to reduce memory usage, when applied to nonlinear methods and algorithms for dimensionality reduction (DR). Due to the incapability of linear DR methods in the preservation of data geometry, the need of effective nonlinear approaches has recently attracted the attention of many researchers, particularly from the Mathematics and Computer Science communities. The common theme of the current nonlinear DR approaches is formulation of certain matrices, called dimensionality reduction kernels (DRK) in terms of the data points, followed by performing spectral decomposition. Hence, for datasets of large size with data points that lie in some high dimensional space, the matrix dimension of the DRK is very large. Typical examples for the need of very high dimensional DRK arise from such applications as processing multispectral imagery data, searching desired text documentary data in the internet, and recognizing human faces from given libraries. For such and many other applications, the matrix dimension of the DRK is so large that computation for carrying out spectral decomposition of the DRK often encounters various difficulties, not only due to the need of significantly large read-only memory (ROM), but also due to computational instability. The main objective of this paper is to introduce the notion of the anisotropic transform (AT) and to develop its corresponding effective and efficient computational algorithms by integrating random embedding with the AT to formulate the randomized anisotropic transform (RAT), in order to reduce the size of the DRK significantly, while preserving local geometries of the given datasets. Illustrations with various examples will also be given in this paper to demonstrate that RAT algorithms dramatically reduce the ROM and CPU requirement, and thus allow fast processing, even on PC and potentially for handhold devices as well.

关键词： Nonlinear dimensionality reduction randomized algorithms Anisotropic transform Data geometry preservation Kernel size reduction Random projection

来源：评论

学校读者我要写书评

暂无评论

A randomized sublinear time parallel GCD algorithm for the EREW PRAM

引用

INFORMATION PROCESSING LETTERS 2010年第5期110卷 198-201页

作者： Sorenson, Jonathan P. Butler Univ Indianapolis IN 46208 USA

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n log log n/log n) time using O (n(6+epsilon)) processors for any epsilon > 0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Parallel algorithms randomized algorithms Algorithm analysis Greatest common divisor Number theoretic algorithms Smooth numbers

来源：评论

学校读者我要写书评

暂无评论

randomized Kaczmarz solver for noisy linear systems

引用

BIT NUMERICAL MATHEMATICS 2010年第2期50卷 395-403页

作者： Needell, Deanna Stanford Univ Dept Stat Stanford CA 94305 USA

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Axa parts per thousand b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.

关键词： randomized algorithms Kaczmarz method Algebraic reconstruction technique

来源：评论

学校读者我要写书评

暂无评论

A randomized Scheduler with Probabilistic Guarantees of Finding Bugs

A Randomized Scheduler with Probabilistic Guarantees of Find...

引用

15th International Conference on Architectural Support for Programming Languages and Operating Systems

作者： Burckhardt, Sebastian Kothari, Pravesh Musuvathi, Madanlal Nagarakatte, Santosh Indian Inst Technol Kanpur 208016 Uttar Pradesh India Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)9781605588391

This paper presents a randomized scheduler for finding concurrency bugs. Like current stress-testing methods, it repeatedly runs a given test program with supplied inputs. However, it improves on stress-testing by finding buggy schedules more effectively and by quantifying the probability of missing concurrency bugs. Key to its design is the characterization of the depth of a concurrency bug as the minimum number of scheduling constraints required to find it. In a single run of a program with n threads and k steps, our scheduler detects a concurrency bug of depth d with probability at least 1/nk(d-1). We hypothesize that in practice, many concurrency bugs (including well-known types such as ordering errors, atomicity violations, and deadlocks) have small bug-depths, and we confirm the efficiency of our schedule randomization by detecting previously unknown and known concurrency bugs in several production-scale concurrent programs.

关键词： algorithms Reliability Verification Concurrency Race Conditions randomized algorithms Testing

来源：评论

学校读者我要写书评

暂无评论

A randomized O(m log m) Time Algorithm for Computing Reeb Graphs of Arbitrary Simplicial Complexes 10

A Randomized O(m log m) Time Algorithm ...

引用

26th Annual Symposium on Computational Geometry

作者： Harvey, William Wang, Yusu Wenger, Rephael Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

ISBN: (纸本)9781450300162

Given a continuous scalar field f : X -> R where X is a topological space, a level set of f is a set {x is an element of X : f(x) = alpha} for some value alpha is an element of R. The level sets of f can be subdivided into connected components. As alpha changes continuously, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f encodes these changes in connected components of level sets. It provides a simple yet meaningful abstraction of the input domain. As such, it has been used in a range of applications in fields such as graphics and scientific visualization. In this paper, we present the first sub-quadratic algorithm to compute the Reeb graph for a function on an arbitrary simplicial complex K. Our algorithm is randomized with an expected running time 0(m log n), where m is the size of the 2-skeleton of K (i.e, total number of vertices, edges and triangles), and n is the number of vertices. This presents a significant improvement over the previous Theta(mn) time complexity for arbitrary complex, matches (although in expectation only) the best known result for the special case of 2-manifolds, and is faster than current algorithms for any other special cases (e.g, 3-manifolds). Our algorithm is also very simple to implement. Preliminary experimental results show that it performs well in practice.

关键词： randomized algorithms Reeb graph topology

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：