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

randomized strategies for the plurality problem

DISCRETE APPLIED MATHEMATICS 2008年第17期156卷 3305-3311页

作者： Kral, Daniel Sgall, Jiri Tichy, Tomas Acad Sci Czech Republic Inst Math CZ-11567 Prague Czech Republic Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci Fac Math & Phys CR-11800 Prague Czech Republic

We consider a game played by two players, Paul and Carol. At the beginning of the game, Carol fixes a coloring of n balls. At each turn, Paul chooses a pair of the balls and asks Carol whether the balls have the same color, Carol truthfully answers his question. Paul's goal is to determine the most frequent (plurality) color in the coloring by asking as few questions as possible. The game is studied in the probabilistic setting when Paul is allowed to choose his next question randomly. We give asymptotically tight bounds both for the case of two colors and many colors. For the balls colored by k colors, we prove a lower bound Omega(kn) on the expected number Of questions;this is asymptotically optimal. For the balls colored by two colors, we provide a strategy for Paul to determine the plurality color with the expected number of 2n/3 + O(root n log n) questions;this almost matches the lower bound 2n/3 - O(root n). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Concrete complexity randomized algorithms Plurality game Majority game

来源：评论

学校读者我要写书评

暂无评论

randomized Matrix Weighted Consensus

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第4期11卷 3536-3549页

作者： Le-Phan, Nhat-Minh Trinh, Minh Hoang Nguyen, Phuoc Doan Hanoi Univ Sci & Technol Sch Elect & Elect Engn Dept Automat Engn Hanoi 11615 Vietnam Viettel Aerosp Inst Nav Guidance & Control Technol Ctr Hanoi 155530 Vietnam FPT Univ AI Dept Quy Nhon Campus Binh Dinh 55117 Vietnam

In this paper, randomized gossip-type matrix weighted consensus algorithms are proposed for both leaderless and leader-follower topologies. First, we introduce the notion of expected matrix weighted network, which captures the multi-dimensional interactions between any two agents in a probabilistic sense. Under some mild assumptions on the distribution of the expected matrix weights and the upper bound of the updating step size, the proposed asynchronous pairwise update algorithms drive the network to achieve a consensus in expectation. An upper bound of the $\epsilon$-convergence time of the algorithm is then derived. Furthermore, the proposed algorithms are applied to the bearing-based network localization and formation control problems. The theoretical results are supported by several numerical examples.

关键词： Consensus algorithm Heuristic algorithms Location awareness Topology Laplace equations Protocols Clocks Matrix weighted consensus multi-agent systems gossip algorithms randomized algorithms network localization formation control

来源：评论

学校读者我要写书评

暂无评论

randomized core reduction for discrete ill-posed problem

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2020年 375卷 112797-000页

作者： Zhang, Liping Wei, Yimin Zhejiang Univ Technol Dept Math Hangzhou 310023 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Shanghai Key Lab Contemporary Appl Math Shanghai 200433 Peoples R China

In this paper, we apply randomized algorithms to approximate the total least squares (TLS) solution of the problem Ax approximate to b in the large-scale discrete ill-posed problems. A regularization technique, based on the multiplicative randomization and the subspace iteration, is proposed to obtain the approximate core problem. In the error analysis, we provide upper bounds for the errors of the solution and the residual of the randomized core reduction. Illustrative numerical examples and comparisons are presented. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Core problem TLS problem randomized algorithms SVD III-posed

来源：评论

学校读者我要写书评

暂无评论

OnlineMin: A Fast Strongly Competitive randomized Paging Algorithm

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 22-40页

作者： Brodal, Gerth Stolting Moruz, Gabriel Negoescu, Andrei Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8200 Aarhus N Denmark Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

关键词： On-line algorithms Competitive analysis Paging randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A randomized COORDINATE DESCENT METHOD WITH VOLUME SAMPLING

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第3期30卷 1878-1904页

作者： Rodomanov, Anton Kropotov, Dmitry Natl Res Univ Higher Sch Econ Samsung HSE Lab Moscow 109028 Russia Lomonosov Moscow State Univ Moscow 119991 Russia

We analyze the coordinate descent method with a new coordinate selection strategy, called volume sampling. This strategy prescribes selecting subsets of variables of certain size proportionally to the determinants of principal submatrices of the matrix, which bounds the curvature of the objective function. In the particular case when the size of the subsets equals one, volume sampling coincides with the well-known strategy of sampling coordinates proportionally to their Lipschitz constants. For the coordinate descent with volume sampling, we establish the convergence rates for both convex and strongly convex problems. Our theoretical results show that, by increasing the size of the subsets, it is possible to accelerate the method up to the factor which depends on the spectral gap between the corresponding largest eigenvalues of the curvature matrix. Several numerical experiments confirm our theoretical conclusions.

关键词： convex optimization unconstrained minimization coordinate descent methods randomized algorithms volume sampling convergence rate

来源：评论

学校读者我要写书评

暂无评论

Constant-time randomized parallel string matching

引用

SIAM JOURNAL ON COMPUTING 1997年第4期26卷 950-960页

作者： Crochemore, M Galil, Z Gasieniec, L Park, K Rytter, W COLUMBIA UNIV DEPT COMP SCINEW YORKNY 10027 MAX PLANCK INST INFORMAT D-66123 SAARBRUCKENGERMANY UNIV WARSAW INST INFORMATPL-02097 WARSAWPOLAND SEOUL NATL UNIV DEPT COMP ENGNSEOUL 151742SOUTH KOREA UNIV LIVERPOOL DEPT COMP SCILIVERPOOL L69 3BXMERSEYSIDEENGLAND UNIV CALIF RIVERSIDE RIVERSIDECA 92521 TEL AVIV UNIV IL-69978 TEL AVIVISRAEL

Given a pattern string of length m. for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log(2) m/log log m). We use this algorithm to obtain the following results (all algorithms below are optimal parallel algorithms on a CRCW PRAM): 1. a deterministic string-matching algorithm which takes O(log log m) time for preprocessing and constant time for text search, which are the best possible in both preprocessing and text search;2. a constant-time deterministic string-matching algorithm in the case where the text length n satisfies n = Omega(m(1+epsilon)) for a constant epsilon > 0;3. a simple string-matching algorithm that has constant time with high probability for random input;4. the main result: a constant-expected-time Las Vegas algorithm for computing the period of the pattern and all witnesses and thus for string matching itself;in both cases, an Omega(log log m) lower bound is known for deterministic algorithms.

关键词： parallel string matching randomized algorithms deterministic samples

来源：评论

学校读者我要写书评

暂无评论

Mixed Deterministic/randomized Methods for Fixed Order Controller Design

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2008年第9期53卷 2033-2047页

作者： Fujisaki, Yasumasa Oishi, Yasuaki Tempo, Roberto Kobe Univ Dept Comp Sci & Syst Engn Kobe Hyogo 6578501 Japan Nanzan Univ Dept Informat Syst & Math Sci Seto 4890863 Japan Politecn Torino CNR IEIIT I-10129 Turin Italy

In this paper, we propose a general methodology for designing fixed order controllers for single-input single-output plants. The controller parameters are classified into two classes: randomized and deterministically designed. For the first class, we study randomized algorithms. In particular, we present two low-complexity algorithms based on the Chernoff bound and on a related bound (often called "log-over-log" bound) which is generally used for optimization problems. Secondly, for the deterministically designed parameters, we reformulate the original problem as a set of linear equations. Then, we develop a technique which efficiently solves it using a combination of matrix inversions and sensitivity methods. A detailed complexity analysis of this technique is carried on, showing its superiority (from the computational point of view) to existing algorithms based on linear programming. In the second part of the paper, these results are extended to H-infinity performance. One of the contributions is to prove that the deterministically designed parameters enjoy a special convex characterization. This characterization is then exploited in order to design fixed order controllers efficiently. We then show further extensions of these methods for stabilization of interval plants. In particular, we derive a simple one-parameter formula for computing the so-called critical frequencies which are required by the algorithms.

关键词： Fixed order controller design H-infinity performance interval plants randomized algorithms stabilization

来源：评论

学校读者我要写书评

暂无评论

A randomized approximate nearest neighbors algorithm

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2013年第3期34卷 415-444页

作者： Jones, Peter W. Osipov, Andrei Rokhlin, Vladimir Yale Univ Dept Math & Comp Sci New Haven CT 06511 USA

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R-d, the algorithm attempts to find k nearest neighbors for each of x(j), where k is a user-specified integer parameter. The algorithm is iterative, and its CPU time requirements are proportional to T . N . (d . (log d) + k . (d + logk) . (log N)) + N . k(2) . (d + logk), with T the number of iterations performed. The memory requirements of the procedure are of the order N . (d + k). A byproduct of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among {x(j)} for an arbitrary point x is an element of R-d. The cost of each such query is proportional to T . (d . (log d) + log(N/k) . k . (d + logk)), and the memory requirements for the requisite data structure are of the order N . (d + k) + T . (d + N). The algorithm utilizes random rotations and a basic divide-and-conquer scheme, followed by a local graph search. We analyze the scheme's behavior for normally distributed points {x(j)}, and illustrate its performance via several numerical examples. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Approximate nearest neighbors randomized algorithms Fast random rotations

来源：评论

学校读者我要写书评

暂无评论

Guaranteed cost regulator design: A probabilistic solution and a randomized algorithm

引用

AUTOMATICA 2007年第2期43卷 317-324页

作者： Fujisaki, Yasumasa Oishi, Yasuaki Kobe Univ Dept Syst & Comp Engn Nada Ku Kobe Hyogo 6578501 Japan Univ Tokyo Dept Math Informat Bunkyo Ku Tokyo 1138656 Japan

This paper presents a gradient-based randomized algorithm to design a guaranteed cost regulator for a plant with general parametric uncertainties. The algorithm either provides with high confidence a probabilistic solution that satisfies the design specification with high probability for a randomly sampled uncertainty or claims that the feasible set of the design parameters is too small to contain a ball with a given radius. In both cases, the number of iterations executed in the algorithm is of polynomial order of the problem size and is independent of the dimension of the uncertainty. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： guaranteed cost regulator probabilistic approach randomized algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

randomized proof-labeling schemes

引用

DISTRIBUTED COMPUTING 2019年第3期32卷 217-234页

作者： Fraigniaud, Pierre Patt-Shamir, Boaz Perry, Mor CNRS Inst Rech Informat Fondamentale Paris France Univ Paris Diderot Paris France Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215-233, 2010. 10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.

关键词： Distributed verification Communication complexity Proof-labeling schemes Non-determinism randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：