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

The scenario approach to robust control design

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2006年第5期51卷 742-753页

作者： Calafiore, Giuseppe C. Campi, Marco C. Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy Univ Brescia Dipartimento Elettron Automaz I-25123 Brescia Italy

This paper proposes a new probabilistic solution, framework for robust control analysis and synthesis problems that can be expressed in the form of minimization of a linear objective subject to convex constraints parameterized by uncertainty terms. This includes the wide class of NP-hard control problems representable by means of parameter-dependent linear matrix inequalities (LMIs). It is shown in this paper that by appropriate sampling of the constraints one obtains a standard convex optimization problem (the scenario problem) whose solution is approximately feasible for the original (usually infinite) set of constraints, i.e., the measure of the set of original constraints that are violated by the scenario solution rapidly decreases to zero as the number of samples is increased. We provide an explicit and efficient bound on the number of samples required to attain a-priori specified levels of probabilistic guarantee of robustness. A rich family of control problems which are in general hard to solve in a deterministically robust sense is therefore amenable to polynomial-time solution, if robustness is intended in the proposed risk-adjusted sense.

关键词： probabilistic robustness randomized algorithms robust control robust convex optimization uncertainty

来源：评论

学校读者我要写书评

暂无评论

Energy balanced data propagation in wireless sensor networks

引用

WIRELESS NETWORKS 2006年第6期12卷 691-707页

作者： Efthymiou, Charilaos Nikoletseas, Sotiris Rolim, Jose Univ Patras Comp Technol Inst GR-26110 Patras Greece Univ Patras Dept Comp Engn & Informat GR-26110 Patras Greece Univ Geneva Geneva Switzerland

We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network's lifetime by avoiding early energy depletion of sensors. We propose a new algorithm that in each step decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap) one-hop transimssions with the direct transimissions to the sink, which are more expensive but "bypass" the sensors lying close to the sink. Note that, in most protocols, these close to the sink sensors tend to be overused and die out early. By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimation can easily be performed by current sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities. The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy-balanced, is also energy efficient.

关键词： wireless sensor networks data propagation energy balance randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Weighted random sampling with a reservoir

引用

INFORMATION PROCESSING LETTERS 2006年第5期97卷 181-185页

作者： Efraimidis, PS Spirakis, PG Democritus Univ Thrace Dept Elect & Comp Engn GR-67100 Xanthi Greece Comp Technol Inst Patras 26221 Greece

In this work, a new algorithm for drawing a weighted random sample of size m from a population of n weighted items, where m <= n, is presented. The algorithm can generate a weighted random sample in one-pass over u... 详细信息

关键词： weighted random sampling reservoir sampling randomized algorithms data streams parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A PTAS for a disc covering problem using width-bounded separators

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第2期11卷 203-217页

作者： Chen, ZX Fu, B Tang, Y Zhu, BH Univ New Orleans Dept Comp Sci New Orleans LA 70148 USA Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA Res Inst Children New Orleans LA 70118 USA Sun Yat Sen Univ Dept Comp Sci Guangzhou 510275 Peoples R China Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane and centers on the grid points, find a subset of discs to maximize the area covered by exactly one disc. This problem originates from the application in digital halftoning, with the best known approximation factor being 5.83 (Asano et al., 2004). We show that if their radii are between two positive constants, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in Fu and Wang (2004), Fu (2006).

关键词： width-bounded separator disc covering approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A new hybrid sampling strategy for PRM planners - To address narrow passages problem

A new hybrid sampling strategy for PRM planners - To address...

引用

3rd International Conference on Informatics in Control, Automation and Robotics

作者： Ali, Sofiane Ahmed Vasselin, Eric Faure, Alain Le Havre Univ GREAH 25 Philippe Lebon StBP 540 F-76058 Le Havre France

ISBN: (纸本)9728865600

The probabilistic path planner (PPP) is a general planning scheme that yields fast robot path planners for a wide variety of problems, involving high degree of freedom articulated robots, non holonomic robots, and multiple robots. This paper presents a new probabilistic approach for finding paths through narrow passages. Our probabilistic planner follows the general framework of probabilistic roadmap (PRM), but to increase sample density in difficult areas like narrow passages, we define two sampling constraints in order to get much more points than a classic PRM gets in such areas. We simulate our planner in 2D environments and the simulations results shows good performance for our planner.

关键词： probabilistic path planner probabilistic roadmap robot path planning randomized algorithms random sampling

来源：评论

学校读者我要写书评

暂无评论

A PTAS for a disc covering problem using width-bounded separators

引用

11th Annual International Conference on Computing and Combinatorics (COCOON 2005)

ISBN: (纸本)9783540280613

关键词： width-bounded separator disc covering approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust network supercomputing with malicious processes

引用

20th International Symposium on Distributed Computing

作者： Konwar, Kishori M. Rajasekaran, Sanguthevar Shvartsman, Alexander A. Univ Connecticut Dept Comp Sci & Engn 371 Fairfield RdUnit 2155 Storrs CT 06269 USA

ISBN: (纸本)3540446249

Internet supercomputing is becoming a powerful tool for harnessing massive amounts of computational resources. However in typical master-worker settings the reliability of computation crucially depends on the ability of the master to depend on the computation performed by the workers. Fernandez, Georgiou, Lopez, and Santos [12,13] considered a system consisting of a master process and a collection of worker processes that can execute tasks on behalf of the master and that may act maliciously by deliberately returning fallacious results. The master decides on the correctness of the results by assigning the same task to several workers. The master is charged one work unit for each task performed by a worker. The goal is to design an algorithm that enables the master to determine the correct result with high probability, and at the least possible cost. Fernandez et al. assume that the number of faulty processes or the probability of a process acting maliciously is known to the master. In this paper this assumption is removed. In the setting with n processes and n tasks we consider two different failure models, viz., model F, where f-fraction, 0 < f < 1/2, of the workers provide faulty results with probability p, 0 < p < 1/2, but the master knows the values of f and p. For model F-a we provide an algorithm-based on the Stopping Rule Algorithm by Dagum, Karp, Luby, and Ross [10]- that can estimate f and p with (is an element of, delta)-approximation, for any 0 < delta < 1 and is an element of > 0. This algorithm runs in O(log n) time, O(log(2) n) message complexity, and O(log(2) n) task-oriented work and O(n log n) total-work complexities. We also provide a randomized algorithm for detecting the faulty processes, i.e., identifying the processes that have non-zero probability of failures in model F-a, with task-oriented work O(n), and time O(log n). A lower bound on the total-work complexity of performing n tasks correctly with high probability is shown. Finally, two rand

关键词： distributed algorithms fault-tolerance randomized algorithms reliability Internet supercomputing

来源：评论

学校读者我要写书评

暂无评论

Stable scheduling policies for maximizing throughput in generalized constrained queueing systems

Stable scheduling policies for maximizing throughput in gene...

引用

IEEE INFOCOM 2006 Conference/25th IEEE International Conference on Computer Communications

作者： Chaporkar, Prasanna Sarkar, Saswati INRIA Paris France Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA

ISBN: (纸本)9781424402212

We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently scheduled. Whenever a queue is scheduled for service, the system transmits a packet and receives a certain reward. Different rewards are obtained for transmitting packets from different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently scheduled queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing throughput is no longer equivalent to maximizing the stability region;we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.

关键词： constrained queueing networks stability throughput optimization wireless multicast randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast edge colorings with fixed number of colors to minimize imbalance 26th

引用

26th International Conference on Foundations of Software Technology and Theoretical Computer Science

作者： Calinescu, Gruia Pelsmajer, Michael J. IIT Dept Comp Sci Chicago IL 60616 USA IIT Dept Math Appl Chicago IL 60616 USA

ISBN: (纸本)9783540499947

We study the following optimization problem: the input is a multigraph G = (V, E) and an integer parameter g. A feasible solution consists of a (not necessarily proper) coloring of E with colors 1, 2,..., g. Denote by d(v, i) the number of edges colored i incident to v. The objective is to minimize Sigma(v is an element of V) max(i) d(v, i), which roughly corresponds to the "imbalance" of the edge coloring. This problem was proposed by Berry and Modiano (INFOCOM 2004), with the goal of optimizing the deployment of tunable ports in optical networks. Following them we call the optimization problem MTPS - Minimum Tunable Port with Symmetric Assignments. Among other results, they give a reduction from Edge Coloring showing that MTPS is NP-Hard and then give a 2-approximation algorithm. We give a (3/2)-approximation algorithm. Key to this problem is the following question: given a multigraph G = (V, E) of maximum degree g, what fraction of the vertices can be properly edge-colored in a coloring with g colors, where a vertex is properly edge-colored if the edges incident to it have different colors? Our main lemma states that there is such a coloring with half of the vertices properly edge-colored. For g : 4, two thirds of vertices can be made properly edge-colored. Our algorithm is based on g Maximum Matching computations (total running time O(gm root n+m/g)) and a local optimization procedure, which by itself gives a 2-approximation. An interesting analysis gives an expected O((gn + m) log (gn + m)) running time for the local optimization procedure.

关键词： approximation algorithms graph theory edge coloring randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

All k-bounded policies are equivalent for self-stabilization

All <i>k</i>-bounded policies are equivalent for self-stabil...

引用

8th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2006)

作者： Beauquier, Joffroy Johnen, Colette Messika, Stephane Univ Paris 11 CNRS LRI Bat 490 F-91405 Orsay France

ISBN: (纸本)3540490183

We reduce the problem of proving the convergence of a randomized self-stabilizing algorithm under k-bounded policies to the convergence of the same algorithm under a specific policy. As a consequence, all k-bounded schedules are equivalent: a given algorithm is self-stabilizing under one of them if and only if it is self-stabilizing under any of them.

关键词： randomized algorithms distributed algorithm self-stabilizing system scheduler

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：