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

On fast and robust information spreading in the Vertex-Congest model

THEORETICAL COMPUTER SCIENCE 2018年 751卷 74-90页

作者： Censor-Hillel, Keren Toukan, Tariq Technion Israel Inst Technol Haifa Israel

This paper initiates the study of the impact of failures on the fundamental problem of information spreading in the Vertex-Congest model, in which in every round, each of the n nodes sends the same O (logn)-bit message to all of its neighbors. We consider a strong failure model, in which links are reliable but nodes fail independently with probability q per round and never recover. Our contribution to coping with failures is twofold. First, we prove that the randomized algorithm which chooses uniformly at random the next message to forward is slow, requiring Omega(n/root k) rounds on some graphs, which we denote by G(n,k) , where k is the vertex-connectivity. Second, we design a randomized algorithm that makes dynamic message choices, with probabilities that change over the execution. We prove that for G(n,k) it requires only a near-optimal number of O(n log(3) n/k) rounds, despite a rate of q = O (k/n log(3) n) failures per round. Our technique of choosing probabilities that change according to the execution is of independent interest. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed computing Information spreading randomized algorithms Vertex-connectivity Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for robust stabilization via static-output-feedbacks

A randomized algorithm for robust stabilization via static-o...

引用

IEEE International Conference on the Science of Electrical Engineering in Israel (ICSEE)

作者： Peretz, Yossi Merzbach, Oria Moyal, Simon Jerusalem Coll Technol Lev Acad Ctr Comp Sci Dept Jerusalem Israel

ISBN: (纸本)9781538663783

A new theorem regarding the robust stability hypercube-tolerance with respect to the specific system defined by the middle-point of a hypercube and a given stabilizing static-output-feedback for it, is proved. Based on the theorem and using the Ray-Shooting Method, a randomized algorithm for the problem of robust stabilization via static-output feedback is suggested. The suggested algorithm has several advantages over existing LMI based algorithms and can easily incorporate structural and other constraints on the controller.

关键词： Continuous-Time Linear Systems State-Space Representation Feedback Stability Robust Stability Simultaneous Stabilization Static Output Feedbacks randomized algorithms Approximation algorithms Convergence In Probability

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Time algorithms for Counting Star Subgraphs via Edge Sampling

引用

ALGORITHMICA 2018年第2期80卷 668-697页

作者： Aliakbarpour, Maryam Biswas, Amartya Shankha Gouleakis, Themis Peebles, John Rubinfeld, Ronitt Yodpinyanee, Anak MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

We study the problem of estimating the value of sums of the form when one has the ability to sample with probability proportional to its magnitude. When , this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when is the degree sequence of a graph, which corresponds to counting the number of p-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a -multiplicative approximation of has query and time complexities . Here, is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, n is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only vertices uniformly gave algorithms with matching lower bounds (Gonen et al. in SIAM J Comput 25:1365-1411, 2011). With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where , and , our upper bound is , in contrast to their lower bound when no random edge queries are available. In addition, we consider the problem of counting the number of directed paths of length two when the graph is directed. This problem is equivalent to estimating the selectivity of a join query between two distinct tables. We prove that the general version of this problem cannot be solved in sublinear time. However, when the ratio between in-degree and out-degree is bounded-or equivalently, when the ratio between

关键词： Subgraphs Approximate counting randomized algorithms Sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On the on-line maintenance scheduling problem

引用

OPTIMIZATION LETTERS 2018年第2期12卷 387-397页

作者： Shamsaei, Fahimeh Telha, Claudio Van Vyve, Mathieu Catholic Univ Louvain Ctr Operat Res & Econometr Voie Roman Pays 34 B-1348 Louvain La Neuve Belgium

A machine instantly serves requests but needs to undergo maintenance after serving a maximum of L requests. We want to maximize the number of requests served. In the on-line version, we prove that serving L requests before placing a maintenance is 0.5-competitive and is best possible for deterministic algorithms. We describe a 0.585-competitive randomized algorithm and show an upper bound of . We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.

关键词： Maintenance scheduling Competitive analysis randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

SDRSAC: Semidefinite-Based randomized Approach for Robust Point Cloud Registration without Correspondences

SDRSAC: Semidefinite-Based Randomized Approach for Robust Po...

引用

IEEE/CVF Conference on Computer Vision and Pattern Recognition

作者： Huu M. Le Thanh-Toan Do Tuan Hoang Ngai-Man Cheung Singapore University of Technology and Design University of Liverpool

ISBN: (纸本)9781728132945

This paper presents a novel randomized algorithm for robust point cloud registration without correspondences. Most existing registration approaches require a set of putative correspondences obtained by extracting invariant descriptors. However, such descriptors could become unreliable in noisy and contaminated settings. In these settings, methods that directly handle input point sets are preferable. Without correspondences, however, conventional randomized techniques require a very large number of samples in order to reach satisfactory solutions. In this paper, we propose a novel approach to address this problem. In particular, our work enables the use of randomized methods for point cloud registration without the need of putative correspondences. By considering point cloud alignment as a special instance of graph matching and employing an efficient semi-definite relaxation, we propose a novel sampling mechanism, in which the size of the sampled subsets can be larger-than-minimal. Our tight relaxation scheme enables fast rejection of the outliers in the sampled sets, resulting in high quality hypotheses. We conduct extensive experiments to demonstrate that our approach outperforms other state-of-the-art methods. Importantly, our proposed method-serves as a generic framework which can be extended to problems with known correspondences.

关键词： Clouds Registration randomized algorithms Graph matching Correspondence RANDOMISING outliers Noise

来源：评论

学校读者我要写书评

暂无评论

Robust Filtering for Markov Jump Systems by randomized Algorithm Approach

Robust Filtering for Markov Jump Systems by Randomized Algor...

引用

American Control Conference

作者： Yanyan Yin Yanqing Liu Xiaoli Luan Song Wang Fei Liu Curtin University GPO Box U1987 Perth WA 6845 Australia Institute of Automation Jiangnan University Wuxi 214122 China

ISBN: (纸本)9781538679012;9781538679265

The issue of probabilistic filtering for a class of Markov jump systems with random uncertain parameters is addressed. A scenario random approach is proposed for designing a probabilistic filter to achieve probabilistic stochastic stabilization, and satisfying an L_2-L_∞ disturbance rejection performance requirement. In Particular, conditions on which the resulting filter based system is stochastically asymptotically stable with a confidence level are established.

关键词： robust filter algorithmic approach randomized algorithms Markov jump Filtration Filters

来源：评论

学校读者我要写书评

暂无评论

SAMPLING CORRECTORS

引用

SIAM JOURNAL ON COMPUTING 2018年第4期47卷 1373-1423页

作者： Canonne, Clement L. Gouleakis, Themis Rubinfeld, Ronitt Stanford Univ Stanford CA 94305 USA MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-6997801 Israel Israel

In many situations, sample data is obtained from a noisy or imperfect source. In order to address such corruptions, this paper introduces the concept of a sampling corrector. Such algorithms use structure that the distribution is purported to have, in order to allow one to make "on-the-fly" corrections to samples drawn from probability distributions. These algorithms then act as filters between the noisy data and the end user. We show connections between sampling correctors, distribution learning algorithms, and distribution property testing algorithms. We show that these connections can be utilized to expand the applicability of known distribution learning and property testing algorithms as well as to achieve improved algorithms for those tasks. As a first step, we show how to design sampling correctors using proper learning algorithms. We then focus on the question of whether algorithms for sampling correctors can be more efficient in terms of sample complexity than learning algorithms for the analogous families of distributions. When correcting monotonicity, we show that this is indeed the case when also granted query access to the cumulative distribution function. We also obtain sampling correctors for monotonicity even without this stronger type of access, provided that the distribution be originally very close to monotone (namely, at a distance O (1 = log(2) n)). In addition to that, we consider a restricted error model that aims at capturing "missing data" corruptions. In this model, we show that distributions that are close to monotone have sampling correctors that are significantly more efficient than achievable by the learning approach. We consider the question of whether an additional source of independent random bits is required by sampling correctors to implement the correction process. We show that for correcting close-to-uniform distributions and close-to-monotone distributions, no additional source of random bits is required, as the samples from the

关键词： randomized algorithms probability distributions property testing learning

来源：评论

学校读者我要写书评

暂无评论

Subspace-Orbit randomized-Based Decomposition for Low-Rank Matrix Approximations 26

Subspace-Orbit Randomized-Based Decomposition for Low-Rank M...

引用

26th European Signal Processing Conference (EUSIPCO)

作者： Kaloorazi, Maboud F. de lamare, Rodrigo C. Pontifical Catholic Univ Rio de Janeiro PUC Rio CETUC Rio De Janeiro RJ Brazil Pontificia Univ Catolica Rio de Janeiro CETUC Rio de Janeiro RJ Brazil Univ York Dept Elect York N Yorkshire England

ISBN: (纸本)9789082797015

In this paper we introduce a novel matrix decomposition algorithm termed Subspace-Orbit randomized Singular Value Decomposition (SOR-SVD). It is computed by using random sampling techniques to give a low-rank approximation to an input matrix. Given a large and dense data matrix of size mxn, SOR-SVD requires a few passes through data to compute a rank-k approximation in O(mnk) floating-point operations. Furthermore, SOR-SVD can utilize advanced computer architectures and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency.

关键词： Matrix decomposition low-rank approximation randomized algorithms numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of M2M Data Collection Networks Using Dynamic Frame-Slotted ALOHA

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING

引用

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING 2018年第2期2卷 493-505页

作者： George, Arun Venkatesh, T. G. Indian Inst Technol Madras Dept Elect Engn Chennai 600036 Tamil Nadu India

We are witnessing an explosion in the growth of the number of connected devices, with the consequent increase of their share in global energy consumption. Thus, it is mandatory that we employ green networking technologies for Internet of Things and machine to machine (M2M) networks. In M2M data collection networks, hundreds or thousands of devices communicate with a data collector (DC). In this regard, dynamic frame slotted Aloha (DFSA) has gained popularity as an energy efficient MAC protocol for M2M data collection networks. In this paper, we carry out performance evaluation of DFSA algorithm. First, we derive analytical bounds on the performance of DFSA. To this end, we employ the properties of binomial distributions and Karp-Upfal-Widgerson inequality. Furthermore, we propose a simple MAC protocol based on DFSA, and analyze the protocol under saturated traffic condition. Using a mathematical model for our proposed protocol, we derive closed form expressions for system throughput, packet delay, and the energy efficiency of the node and the DC. The analysis is validated through extensive simulation.

关键词： Dynamic frame slotted ALOHA M2M sensor networks randomized algorithms Karp-Upfal-Widgerson inequalities

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for the scaffolding problem and its generalizations

引用

THEORETICAL COMPUTER SCIENCE 2018年 734卷 131-141页

作者： Chen, Zhi-Zhong Harada, Youta Guo, Fei Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Tianjin Univ Sch Comp Sci & Technol Tianjin Peoples R China City Univ Hong Kong Dept Comp Sci 83 Tat Chee Ave Hong Kong Hong Kong Peoples R China Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China

Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theoretical problem has been proposed: Given an edge-weighted complete graph G and a perfect matching D of G, we wish to find a Hamiltonian path P in G such that all edges of D appear in P and the total weight of edges in P but not in D is maximized. This problem is NP-hard and the previously best polynomial-time approximation algorithm for it achieves a ratio of 1/2. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of 5-5 is an element of/9-8 is an element of for any constant 0 < is an element of < 1. Several generalizations of the problem have also been introduced in the literature and we present polynomial-time approximation algorithms for them that achieve better approximation ratios than the previous bests. In particular, one of the algorithms answers an open question. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms randomized algorithms Scaffolding Matchings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：