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

Probabilistic output admissible set for systems with time-varying uncertainties

SYSTEMS & CONTROL LETTERS 2008年第4期57卷 315-321页

作者： Hatanaka, Takeshi Takaba, Kiyotsugu Tokyo Inst Technol Dept Mech & Control Engn Meguro Ku Tokyo 152 Japan Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Sakyo Ku Kyoto 6068501 Japan

This paper considers time-varying uncertain constrained systems, and develops a method for computing a probabilistic output admissible (POA) set. This set consists of the initial states probabilistically assured to satisfy the constraint. The time-invariant counterpart has already been investigated in Hatanaka and Takaba [Computations of probabilistic output admissible set for uncertain constrained systems, Automatica 44 (2) (2008), to appear]. We first define the POA set for time-varying uncertainties with finite dimensional probability space. Then, we show that an algorithm similar to Hatanaka and Takaba [Computations of probabilistic output admissible set for uncertain constrained systems, Automatica 44 (2) (2008), to appear] provides the POA set also in the time-varying case, as long as an upper bound of a what we call future output admissibility (FOA) index is available. We moreover present two methods for computing the upper bound of the FOA index: probabilistic and deterministic methods. A numerical simulation demonstrates the effectiveness of our algorithm. (C) 2007 Elsevier B.V. All rights reserved.

关键词： constrained system probabilistic output admissible set maximal output admissible set time-varying uncertainty randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Testing whether a digraph contains H-free k-induced subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期407卷 545-553页

作者： Lin, Hong-Yiu Lyuu, Yuh-Dauh Ma, Tak-Man Ti, Yen-Wu Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan MediaTek Inc Hsinchu Taiwan

A subgraph induced by k vertices is called a k-induced subgraph. We prove that determining if a digraph G contains H-free k-induced subgraphs is Omega(N-2)-evasive. Then we construct an is an element of-tester to test this property. (An E-tester fora property Pi is guaranteed to distinguish, with probability at least 2/3, between the case of G satisfying Pi and the case of G being is an element of-far from satisfying Pi.)The query complexity of the E-tester is independent of the size of the input digraph. An (E,)is an element of-tester fora property Pi is an E-tester for Pi that is furthermore guaranteed to accept with probability at least 2/3 any input that is delta-close to satisfying Pi. This paper presents an (is an element of, delta)-tester for whether a digraph contains H-free k-induced subgraphs. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Directed graphs Property testing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Unified Theorem on SDP Rank Reduction

引用

MATHEMATICS OF OPERATIONS RESEARCH 2008年第4期33卷 910-920页

作者： So, Anthony Man-Cho Ye, Yinyu Zhang, Jiawei Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA NYU Stern Sch Business Dept Informat Operat & Management Sci New York NY 10012 USA

We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several well-known results in the literature. In particular, it contains as special cases the Johnson-Lindenstrauss lemma on dimensionality reduction, results on low-distortion embeddings into low-dimensional Euclidean space, and approximation results on certain quadratic optimization problems.

关键词： semidefinite programming low-rank matrices randomized algorithm metric embedding quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

Research on selecting initial points for k-means clustering

Research on selecting initial points for k-means clustering

引用

7th International Conference on Machine Learning and Cybernetics

作者： Wang, Shou-Qiang Zhu, Da-Ming Shandong Univ Sch Comp Sci & Technol Jinan 250100 Peoples R China

ISBN: (纸本)9781424420957

Clustering analysis is one of the important problems in the fields of data mining and machine learning. There are many different clustering methods. Among them, k-means clustering is one of the most popular schemes owing to its simple and practicality. This paper investigates the approximate algorithm for the k-means clustering by means of selecting the k initial points from the input point set. An expected 2-approximation algorithm is presented in this paper. Meanwhile, an efficient algorithm for selecting the initial points is also proposed. At last some experimental results are given to test the valid of these algorithms.

关键词： clustering k-means clustering randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast distributed approximation algorithm for minimum spanning trees

引用

20th International Symposium on Distributed Computing

作者： Khan, Maleq Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)3540446249

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Omega(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H is an element of [1, Theta(log n)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal (O) over tilde (D(G)) time.

关键词： minimum spanning tree distributed approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for robust feasibility problems with general nonconvex constraints

Randomized algorithms for robust feasibility problems with g...

引用

Annual Conference on the Society-of-Instrument-and-Control-Engineers

作者： Wada, Takayuki Fujisaki, Yasumasa Kobe Univ Grad Sch Sci & Technol Kobe Hyogo 6578501 Japan Kobe Univ Grad Sch Engn Kobe Hyogo 6578501 Japan

ISBN: (纸本)9784907764289

A class of robust feasibility problems is considered, which is to find a design variable satisfying a parameter-dependent constraint for all parameter values. A randomized algorithm for solving the problem with a general nonconvex constraint is proposed, where random samples of candidates of the design variable and uncertain parameters are used. The algorithm stops in a finite number of iterations. Then, it gives a design variable satisfying the constraint for almost all parameter values with a prescribed confidence or says that the problem is infeasible in a probabilistic sense.

关键词： robust control robust feasibility problem randomized algorithm probabilistic solution probabilistic infeasibility

来源：评论

学校读者我要写书评

暂无评论

Enabling information confidentiality in publish/subscribe overlay services

Enabling information confidentiality in publish/subscribe ov...

引用

IEEE International Conference on Communications (ICC 2008)

作者： Zhang, Hui Sharma, Abhishek Chen, Haifeng Jiang, Guofei Meng, Xiaoqiao Yoshihira, Kenji NEC Labs Amer Princeton NJ USA Univ Southern Calif Los Angeles CA USA NEC Lab Amer Princeton NJ USA

ISBN: (纸本)9781424420742

"Alice has a piece of valuable information which she is willing to sell to anyone who is interested in;she is too busy and wants to ask Bob, a professional broker, to sell that information for her;but Alice is in a dilemma where she cannot trust Bob with that information but Bob cannot help her find her customers without knowing that information." In this paper, we propose a security mechanism called information foiling to address new confidentiality problems arising in pub/sub overlay services [1]. Information foiling extends Rivest's "Chaffing and Winnowing" [2], and its basic idea is to carefully generate a set of fake messages to hide an authentic message. Information foiling requires no modification inside the broker network so that the routing/filtering capabilities of broker nodes remains intact. We formally present the information foiling mechanism in the context of publish/subscribe overlay services, and discuss its applicability in other Internet applications. For publish/subscribe applications, we propose a suite of optimal schemes for fake message generation in different scenarios. Real-world data are used in our evaluation to demonstrate the effectiveness of the proposed schemes.

关键词： security confidentiality publish/subscribe randomized algorithm data privacy

来源：评论

学校读者我要写书评

暂无评论

Distributed average consensus in sensor networks with quantized inter-sensor communication

Distributed average consensus in sensor networks with quanti...

引用

33rd IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Kar, Soummya Moura, Jose M. F. Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA

ISBN: (纸本)9781424414833

The paper studies distributed average consensus in sensor networks, when the sensors exchange quantized data at each time step. We show that randomizing the exchanged sensor data by adding a controlled amount of dither results in almost sure (a.s.) convergence of the protocol, if the network is connected. We explicitly characterize the mean-squared error (with respect to the desired consensus average) and show that, by tuning certain parameters associated with the protocol, the mean-squared error can be made arbitrarily small. We study the trade-offs between the rate of convergence and the resulting mean-squared error. The sensor network topology plays an important role in determining the convergence rate of the algorithm. Our approach, based on the convergence of controlled Markov processes, is very generic and can be applied to many other situations of imperfect communication. Finally, we present numerical studies, which verify our theoretical results.

关键词： distributed consensus quantized information exchange topology Laplacian randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Secure Communication Over Radio Channels

Secure Communication Over Radio Channels

引用

27th Annual ACM Symposium on Principles of Distributed Computing

作者： Dolev, Shlomi Gilbert, Seth Guerraoui, Rachid Newport, Calvin Ben Gurion Univ Negev IL-84105 Beer Sheva Israel EPFL IC Lausanne Switzerland MIT CSAIL Cambridge MA USA

ISBN: (纸本)9781595939890

We study the problem of secure communication in a multichannel, single-hop radio network with a malicious adversary that, call cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and anthenticated manner. It runs in O(vertical bar E vertical bar t(2) log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t < C the number of channels on which the adversary can participate in each round. We show how to use f-AME to establish a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. The resulting service requires O(nt(3) log n) rounds for the setup phase, and O(t log n) rounds for an arbitrary pair to communicate. By contrast, existing solutions rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious.

关键词： Wireless Radio Networks Malicious (Byzantine) Interference randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized probe selection algorithm for microarray design

引用

JOURNAL OF THEORETICAL BIOLOGY 2007年第3期248卷 512-521页

作者： Gasieniec, Leszek Li, Cindy Y. Sant, Paul Wong, Prudence W. H. Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

DNA microarray technology, originally developed to measure the level of gene expression, has become one of the most widely used tools in genomic study. The crux of microarray design lies in how to select a unique probe that distinguishes a given genomic sequence from other sequences. Due to its significance, probe selection attracts a lot of attention. Various probe selection algorithms have been developed in recent years. Good probe selection algorithms should produce a small number of candidate probes. Efficiency is also crucial because the data involved are usually huge. Most existing algorithms are usually not sufficiently selective and quite a large number of probes are returned. We propose a new direction to tackle the problem and give an efficient algorithm based on randomization to select a small set of probes and demonstrate that such a small set of probes is sufficient to distinguish each sequence from all the other sequences. Based on the algorithm, we have developed probe selection software RANDPS, which runs efficiently in practice. The software is available on our website (http://***/similar to cindy/RandPS/***). We test our algorithm via experiments on different genomes (Escherichia coli, Saccharamyces cercvisiae, etc.) and our algorithm is able to output unique probes for most of the genes efficiently. The other genes can be identified by a combination of at most two probes. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： randomized algorithm probe selection microarray design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：