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

Robustly asymptotically stable finite-horizon MPC

AUTOMATICA 2006年第12期42卷 2189-2194页

作者： Kanev, S. Verhaegen, M. Delft Univ Technol DCSC NL-2628 CD Delft Netherlands

This paper presents a robustly stable finite-horizon model predictive control (MPC) scheme for linear uncertain systems, in which the uncertainty is not restricted to some specific uncertainty class (polytopic, affine, LFT, etc.). The only requirement is that the state-space matrices remain bounded over the uncertainty set. Suitable constraints are added to the MPC cost function to impose robust asymptotic stability and to deal with input/output constraints. The resulting optimization problem is solved at each time instant in a probabilistic framework using an iterative randomized ellipsoid algorithm (REA). The method is compared in simulation to the existing approach of Kothare, Balakrishnan and Morari [(1996). Robust constrained model predictive control using linear matrix inequalities. Automatica, 32(10), 1361-1379]. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： model predictive control uncertainty robustness stability randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Complex quadratic optimization and semidefinite programming

引用

SIAM JOURNAL ON OPTIMIZATION 2006年第3期16卷 871-890页

作者： Zhang, SZ Huang, YW Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson [J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-form formula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an [m(2)(1 - cos 2 pi/m)/8 pi]-approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of pi/4 approximate to 0.7854, which is better than the ratio of 2/pi approximate to 0.6366 for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.

关键词： Hermitian quadratic functions approximation ratio randomized algorithms complex semidefinite programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Online conflict-free coloring for intervals

引用

SIAM JOURNAL ON COMPUTING 2006年第5期36卷 1342-1359页

作者： Chen, Ke Fiat, Amos Kaplan, Haim Levy, Meital Matousek, Jiri Mossel, Elchanan Pach, Janos Sharir, Micha Smorodinsky, Shakhar Wagner, Uli Welzl, Emo Univ Illinois Dept Comp Sci Urbana IL 61801 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA NYU Courant Inst Math Sci New York NY 10012 USA Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Swiss Fed Inst Technol Inst Theoret Comp Sci Zurich Switzerland

We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple ( deterministic) approach may perform rather poorly, requiring Omega(root n) colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses O(log(2) n) colors, and the second is randomized and uses O( log n) colors with high probability. We also show that the O(log(2) n) bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

关键词： conflict-free coloring online algorithms randomized algorithms branching processes

来源：评论

学校读者我要写书评

暂无评论

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

引用

INFORMATION PROCESSING LETTERS 2006年第4期97卷 161-169页

作者： Lesh, N Mitzenmacher, A Harvard Univ Dept Comp Sci Cambridge MA 02138 USA Mitsubishi Elect Res Labs Cambridge MA 02139 USA

We introduce BubbleScarch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness. (c) 2005 Published by Elsevier B.V.

关键词： greedy algorithms priority algorithms randomized algorithms heuristic algorithms GRASP algorithms

来源：评论

学校读者我要写书评

暂无评论

An energy efficient leader election protocol for radio network with a single transceiver

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2006年第5期E89A卷 1355-1361页

作者： Bordim, Jacir Luiz Ito, Yasuaki Nakano, Koji Univ Brasilia Dept Comp Sci BR-70910900 Brasilia DF Brazil Hiroshima Univ Sch Engn Higashihiroshima 7398527 Japan

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1 - 1/f (f >= 1), in log log n + o(log log n) + O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver. our leader election protocol still runs, with probability exceeding 1 - 1/f (f >= 1) in log log n + o(log log n) + O(log f) time f slots. Moreover. our leader election protocol needs only expected 0(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(n log log n) total awake time slots. Since every leader election protocol needs at least Omega(n) awake time slots. our leader election protocol is optimal in terms of the expected awake time slots.

关键词： adhoc networks collision detection distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix

引用

SIAM JOURNAL ON COMPUTING 2006年第1期36卷 158-183页

作者： Drineas, Petros Kannan, Ravi Mahoney, Michael W. Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA Yale Univ Dept Math New Haven CT 06520 USA

In many applications, the data consist of ( or may be naturally formulated as) an m x n matrix A. It is often of interest to find a low-rank approximation to A, i.e., an approximation D to the matrix A of rank not greater than a specified rank k, where k is much smaller than m and n. Methods such as the singular value decomposition (SVD) may be used to find an approximation to A which is the best in a well-defined sense. These methods require memory and time which are superlinear in m and n;for many applications in which the data sets are very large this is prohibitive. Two simple and intuitive algorithms are presented which, when given an m x n matrix A, compute a description of a low-rank approximation D* to A, and which are qualitatively faster than the SVD. Both algorithms have provable bounds for the error matrix A - D*. For any matrix X, let parallel to X parallel to(F) and parallel to X parallel to(2) denote its Frobenius norm and its spectral norm, respectively. In the first algorithm, c columns of A are randomly chosen. If the m x c matrix C consists of those c columns of A ( after appropriate rescaling), then it is shown that from (CC)-C-T approximations to the top singular values and corresponding singular vectors may be computed. From the computed singular vectors a description D* of the matrix A may be computed such that rank(D*) <= k and such that parallel to A - D*parallel to(2)(xi) <= min (D: rank(D) <= k) parallel to A - D parallel to(2)(xi) + poly(k, 1/ c)parallel to A parallel to(2)(F) holds with high probability for both xi = 2, F. This algorithm may be implemented without storing the matrix A in random access memory ( RAM), provided it can make two passes over the matrix stored in external memory and use O(cm + c(2)) additional RAM. The second algorithm is similar except that it further approximates the matrix C by randomly sampling r rows of C to form a r x c matrix W. Thus, it has additional error, but it can be implemented in three passes ove

关键词： randomized algorithms Monte Carlo methods massive data sets singular value decomposition

来源：评论

学校读者我要写书评

暂无评论

An improvement of the tree code construction

引用

INFORMATION PROCESSING LETTERS 2006年第3期99卷 92-95页

作者： Peczarski, Marcin Warsaw Univ Inst Informat PL-02097 Warsaw Poland

An improvement of the randomized construction for tree codes is presented. This construction, in contrary to the original one, almost surely gives a good code and uses smaller alphabet. (c) 2006 Elsevier B.V. All righ... 详细信息

关键词： combinatorial problems fault tolerance randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient polynomial time algorithms computing industrial-strength primitive roots

引用

INFORMATION PROCESSING LETTERS 2006年第2期97卷 41-45页

作者： Dubrois, J Dumas, JG Univ Grenoble 1 Lab Modelisat & Calcul F-38041 Grenoble France Axalto F-92542 Montrouge France

E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of Z/pZ. E. Bach Suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to I as necessary. In particular we present an asymptotically O-similar to(root 1/epsilon log(p) + log(2)(p)) algorithm providing primitive roots of p with probability of correctness greater than I - epsilon and several 0(log(alpha)(p)), alpha <= 5.23, algorithms computing "Industrial-strength" primitive roots. (c) 2005 Elsevier B.V. All rights reserved.

关键词： computational complexity cryptography randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication

引用

SIAM JOURNAL ON COMPUTING 2006年第1期36卷 132-157页

Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These algorithms make more efficient use of computational resources, such as the computation time, random access memory ( RAM), and the number of passes over the data, than do previously known algorithms for these problems. In this paper, we devise two algorithms for the matrix multiplication problem. Suppose A and B ( which are m x n and n x p, respectively) are the two input matrices. In our main algorithm, we perform c independent trials, where in each trial we randomly sample an element of {1, 2,..., n} with an appropriate probability distribution P on {1, 2,..., n}. We form an m x c matrix C consisting of the sampled columns of A, each scaled appropriately, and we form a c x n matrix R using the corresponding rows of B, again scaled appropriately. The choice of P and the column and row scaling are crucial features of the algorithm. When these are chosen judiciously, we show that CR is a good approximation to AB. More precisely, we show that parallel to AB - CR parallel to(F) = O(parallel to A parallel to(F)parallel to B parallel to(F) /root c), where parallel *** to F denotes the Frobenius norm, i. e., parallel to A parallel to(2)(F) = Sigma(i, j) A(ij)(2). This algorithm can be implemented without storing the matrices A and B in RAM, provided it can make two passes over the matrices stored in external memory and use O(c( m+ n+ p)) additional RAM to construct C and R. We then present a second matrix multiplication algorithm which is similar in spirit to our main algorithm. In addition, we present a model (the pass-efficient model) in which the efficiency of these and other approximate matrix algorithms may be studied and which we argue is well suited to many applications involving massive data sets. In this model, the scarce computational resources are the number of passes over the data and the additional space an

关键词： randomized algorithms Monte Carlo methods massive data sets streaming models matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for on-line graph problems with application to on-line circuit and optical routing

引用

SIAM JOURNAL ON COMPUTING 2006年第2期36卷 354-393页

作者： Bartal, Yair Fiat, Amos Leonardi, Stefano Hebrew Univ Jerusalem Sch Comp Sci Jerusalem Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ Roma La Sapienza Dipartimento Informat & Sistemist Rome Italy

We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems, and we apply such results to on-line virtual circuit and optical routing problems. Lund and Yannakakis [The approximation of maximum subgraph problems, in Proceedings of the 20th International Colloquium on Automata, Languages and Programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi-e. g., independent set, planar, acyclic, bipartite. We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H of G is presented on-line, vertex by vertex. The on-line algorithm must choose a subset of the vertices of H, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property p. Furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. Irrespective of the time complexity, we show an Omega(n epsilon()) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. As a consequence, we obtain an Omega(n(epsilon)) lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks. Similar lower bounds are obtained for on-line optical routing as well.

关键词： on-line computation graph problems network optimization competitive analysis randomized algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：