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

Matchings meeting quotas and their impact in the blow-up lemma

SIAM JOURNAL ON COMPUTING 2001年第2期31卷 428-446页

作者： Rödl, V Rucinski, A Wagner, M Emory Univ Dept Math & Comp Sci Atlanta GA 30322 USA Adam Mickiewicz Univ Poznan Dept Discrete Math PL-60769 Poznan Poland Univ Wisconsin La Crosse WI 54601 USA

A bipartite graph G = (U,V;E) is called epsilon -regular if the edge density of every sufficiently large induced subgraph differs from the edge density of G by no more than. If, in addition, the degree of each vertex in G is between (d-epsilon) n and (d+epsilon) n, where d is the edge density of G and |U| = |V| = n, then G is called super (d,epsilon)-regular. In [Combinatorica, 19(1999), pp. 437-452] it was shown that if S subset ofU and T subset ofV are subsets of vertices in a super-regular bipartite graph G = ( U, V;E), and if a perfect matching M of G is chosen randomly, then the number of edges of M that go between the sets S and T is roughly |S||T|/n. In this paper, we derandomize this result using the Erdos-Selfridge method of conditional probabilities. As an application, we give an alternative constructive proof of the blow-up lemma of Komlos, Sarkozy, and Szemeredi (see [ Combinatorica, 17 (1997), pp. 109-123] and [Random Structures algorithms, 12 (1998), pp. 297-312]).

关键词： regular graphs perfect matchings conditional probabilities randomized algorithms derandomization blow-up lemma

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

引用

ALGORITHMICA 1997年第1期17卷 67-87页

作者： BangJensen, J ElHaddad, M Manoussakis, Y Przytycka, TM UNIV PARIS 11 LRIF-91405 ORSAYFRANCE

We give an O (log(4) n)-time O(n(2))-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph, B, provided that a factor of B (i.e., a collection of vertex disjoint cycles covering the vertex set of B)is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite digraph in time O(r(n)) using p(n) processors can be used to check the existence of a perfect matching in a bipartite graph in time O(r(n) + n(2)/p(n)) using p(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph.

关键词： graph algorithms Hamilton cycle parallel algorithms semicomplete bipartite graphs randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fair service for mice in the presence of elephants

引用

INFORMATION PROCESSING LETTERS 2006年第3期99卷 96-101页

作者： Voorhies, Seth Lee, Hyunyoung Klappenecker, Andreas Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Univ Denver Dept Comp Sci Denver CO 80208 USA

We show how randomized caches can be used in resource-poor partial-state routers to provide a fair share of bandwidth to short-lived flows that are known as mice when long-lived flows known as elephants are present. (... 详细信息

关键词： algorithms randomized algorithms caching probabilistic queues

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL-DESIGN OF CHECKS FOR ERROR-DETECTION AND LOCATION IN FAULT-TOLERANT MULTIPROCESSOR SYSTEMS

引用

IEEE TRANSACTIONS ON COMPUTERS 1993年第7期42卷 780-793页

作者： SITARAMAN, RK JHA, NK PRINCETON UNIV DEPT ELECT ENGNPRINCETONNJ 08544

Designing checks to detect or locate errors in the data plays an important role in the design of fault tolerant systems. Recently, the problem of synthesizing the data-check (DC) relationship has received a lot of attention in the context of a natural paradigm for concurrent error detection/location known as algorithm-based fault tolerance (ABFT). Banerjee and Abraham have shown that an ABFT scheme can be modeled as a tripartite graph consisting of processors (P), data (D), and checks (C). Any technique for designing ABFT systems requires a procedure for synthesizing a DC relationship, which not only has a low overhead but also has all the properties required by the designer. The main contribution of this work is to propose a simple and novel algorithm called RANDGEN to generate DC graphs. This synthesis approach itself is very fast and can be fully parallelized. By simply varying its parameters, the same algorithm RANDGEN can produce DC graphs with a wide spectrum of properties, many of which have been considered very important in recent ABFT designs. RANDGEN produces s-error-detectable DC graphs with asymptotically the least number of checks for the first time. RANDGEN can also produce s-error-locatable DC graphs using only a small number of checks. This is the first general procedure for producing error-locatable graphs for any value of s. Another important outstanding problem in DC graph design is providing fast and practical methods for actually locating the errors in the data from the output pattern at the checks. We show that RANDGEN can be used to design DC graphs, which permit easy diagnosis, again with a small number of checks. It has been pointed out previously that ''uniform'' checks may simplify the design of the ABFT system. We show how RANDGEN can be modified very simply to produce uniform s-error-detectable/locatable DC graphs. Finally, we show how one can generalize these results to synthesize strictly s-error-detectable/locatable DC graphs which ca

关键词： ALGORITHM-BASED FAULT TOLERANCE CHECKSUM ENCODING CONCURRENT ERROR DETECTION CONCURRENT ERROR LOCATION MAJORITY DIAGNOSIS randomized algorithms UNIFORM CHECKS

来源：评论

学校读者我要写书评

暂无评论

Resolution of conflicts involving many aircraft via semidefinite programming

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2001年第1期24卷 79-86页

作者： Frazzoli, E Mao, ZH Oh, JH Feron, E MIT Dept Aeronaut & Astronaut Informat & Decis Syst Lab Int Ctr Air Transportat Cambridge MA 02139 USA MIT Dept Mech Engn Cambridge MA 02139 USA

Aircraft conflict detection and resolution is currently attracting the interest of many air transportation service providers and is concerned with the following question: Given a set of airborne aircraft and their intended trajectories, what control strategy should be followed by the pilots and the air traffic service provider to prevent the aircraft from coming too close to each other? This paper addresses this problem by presenting a resolution methodology whereby each aircraft proposes its desired heading while a centralized air traffic control authority resolves any conflict arising between aircraft, while minimizing the deviation between desired and conflict-free heading for each aircraft. The resolution methodology relies on a combination of convex programming and randomized searches: It is shown that a version of the planar, multiaircraft conflict resolution problem, accounting for all possible crossing patterns among aircraft, might be recast as a nonconvex, quadratically constrained quadratic program. For this type of problem, there exist efficient numerical relaxations, based on semidefinite programming, that provide lower bounds on the best achievable objective. These relaxations also lead to a random search technique to compute feasible, locally optimal, and conflict-free strategies. This approach is demonstrated on numerical examples and discussed.

关键词： Airborne Aircraft Quadratic Programming Air Transportation System randomized algorithms Convex Optimization Pilot Global Navigation Satellite System Navigation Beacon Aircraft Navigation Guidance Laws

来源：评论

学校读者我要写书评

暂无评论

Stochastic algorithms for robustness of control performances

引用

AUTOMATICA 2009年第6期45卷 1407-1414页

作者： Piccoli, Benedetto Zadarnowska, Katarzyna Gaeta, Matteo Wroclaw Univ Technol Inst Comp Engn Control & Robot PL-50372 Wroclaw Poland CNR Ist Applicaz Calcolo Mauro Picone I-00161 Rome Italy Univ Salerno Dept Informat Engn & Appl Math I-88084 Fisciano SA Italy

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to "difficult" control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the "intractable" problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Control system Robustness randomized algorithms Stochastic algorithms Stochastic differential equations

来源：评论

学校读者我要写书评

暂无评论

Broadcasting in dynamic radio networks

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2009年第4期75卷 213-230页

作者： Clementi, Andrea E. F. Monti, Angelo Pasquale, Francesco Silvestri, Riccardo Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Roma La Sapienza Dipartimento Informat I-00133 Rome Italy

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand. theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few. In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsasser and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992. In both cases we provide tight bounds on the completion time of randomized broadcast protocols. (C) 2008 Elsevier Inc. All rights reserved.

关键词： randomized algorithms Dynamic networks Radio networks Random graphs

来源：评论

学校读者我要写书评

暂无评论

MULTIPLE COMMUNICATION IN MULTIHOP RADIO NETWORKS

引用

SIAM JOURNAL ON COMPUTING 1993年第4期22卷 875-887页

作者： BARYEHUDA, R ISRAELI, A ITAI, A TECHNION ISRAEL INST TECHNOL DEPT ELECT ENGNIL-32000 HAIFAISRAEL

Two tasks of communication in a multihop synchronous radio network are considered: Point-to-point communication and broadcast (sending a message to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically. Let n, D, and DELTA be the number of nodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS tree is constructed. This phase takes O((n + D log n) log DELTA) time. After the setup, k point-to-point transmissions require O((k + D) log DELTA) time on the average. Therefore the network allows a new transmission every O(log DELTA) time slots. Also, k broadcasts require an average of O((k + D) log DELTA log n) time. Hence the average throughput of the network is a broadcast every O(log DELTA log n) time slots. Both protocols pipeline the messages along the BFS tree. They are always successful on the graph spanned by the BFS tree. Their probabilistic behavior refers only to the running time. Using the above protocols the ranking problem is solved in O(n log n log DELTA) time. The performance analysis of both protocols constitutes a new application of queueing theory.

关键词： RADIO NETWORKS BROADCAST POINT-TO-POINT ROUTING DISTRIBUTED algorithms AVERAGE CASE ANALYSIS QUEUING THEORY randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic model predictive control of LPV systems via scenario optimization

引用

AUTOMATICA 2013年第6期49卷 1861-1866页

作者： Calafiore, Giuseppe C. Fagiano, Lorenzo Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy Swiss Fed Inst Technol Automat Control Lab Zurich Switzerland Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

A stochastic receding-horizon control approach for constrained Linear Parameter Varying discrete-time systems is proposed in this paper. It is assumed that the time-varying parameters have stochastic nature and that the system's matrices are bounded but otherwise arbitrary nonlinear functions of these parameters. No specific assumption on the statistics of the parameters is required. By using a randomization approach, a scenario-based finite-horizon optimal control problem is formulated, where only a finite number M of sampled predicted parameter trajectories ('scenarios') are considered. This problem is convex and its solution is a priori guaranteed to be probabilistically robust, up to a user-defined probability level p. The p level is linked to M by an analytic relationship, which establishes a tradeoff between computational complexity and robustness of the solution. Then, a receding horizon strategy is presented, involving the iterated solution of a scenario-based finite-horizon control problem at each time step. Our key result is to show that the state trajectories of the controlled system reach a terminal positively invariant set in finite time, either deterministically, or with probability no smaller than p. The features of the approach are illustrated by a numerical example. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Model predictive control Linear parameter-varying systems randomized algorithms Scenario optimization Random convex programs

来源：评论

学校读者我要写书评

暂无评论

Research on probabilistic methods for control system design

引用

AUTOMATICA 2011年第7期47卷 1279-1293页

作者： Calafiore, Giuseppe C. Dabbene, Fabrizio Tempo, Roberto Politecn Torino IEIIT CNR I-10129 Turin Italy Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy

A novel approach based on probability and randomization has emerged to synergize with the standard deterministic methods for control of systems with uncertainty. The main objective of this paper is to provide a broad perspective on this area of research known as "probabilistic robust control", and to address in a systematic manner recent advances. The focal point is on design methods, based on the interplay between uncertainty randomization and convex optimization, and on the illustration of specific control applications. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： randomized algorithms Control of uncertain systems Optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：