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

randomized approximation algorithms for planar visibility counting problem

THEORETICAL COMPUTER SCIENCE 2018年 707卷 46-55页

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Sharif Univ Technol Dept Comp Engn Tehran Iran Sharif Univ Technol Dept Math Sci Tehran Iran Inst Res Fundamental Sci IPM Sch Math Tehran Iran

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O (log n) query time using O(n(4) log n) preprocessing time and O(n(4)) space. Gudmundsson and Morin (2010) [101 proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 <= alpha <= 1, their algorithm answers any query in O-epsilon (m((1-alpha)/2)) time with O (epsilon)(M1+alpha) of preprocessing time and space, where epsilon > 0 is a constant that can be made arbitrarily small and O-epsilon (f (n)) = O (f (n)n(epsilon)) and in m = O (n(2)) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 <= beta <= 2/3 and 0 < delta <= 1, and the expected preprocessing time, the expected space, and the expected query time are O (m(2-3 beta/2) log m), O(m(2-3 beta/2)), and O (1/delta(2)m(beta/2) log m), respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p, denoted by m(p), exactly, if m(p) <= 3/delta(2)m(beta/2) log(2m). Otherwise, it computes an approximated value, m(p), such that with the probability of at least 1 - 1/m, we have (1 - delta)m(p) <= m'(p) <= (2 + 2 delta)m(p). The preprocessing time and space of the second algorithm are O(n(2) log n) and O(n(2)), respectively. This algorithm computes the exact value of m(p) if m(p) <= 1/delta(2) root n log n, otherwise it returns an approximated value m ''(p) in expected O(1/delta(2)root n log n) time, such that with the probability at least 1 - 1/log n, we

关键词： Computational geometry Visibility randomized algorithm Approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient randomized Switching for Maximizing Lifetime in Tree-Based Wireless Sensor Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2015年第5期23卷 1401-1415页

作者： Imon, Sk Kajal Arefin Khan, Adnan Di Francesco, Mario Das, Sajal K. Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA Aalto Univ Dept Comp Sci & Engn Aalto 00076 Finland Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA

In most wireless sensor network (WSN) applications, data are typically gathered by sensor nodes and reported to a data collection point called sink. To support such a data collection pattern, a tree structure rooted at the sink is defined. Depending on various factors, including the WSN topology and the availability of resources, the energy consumption of nodes in different paths of the data collection tree may vary largely, thus affecting the overall network lifetime. This paper addresses the problem of lifetime maximization of WSNs based on data collection trees. Specifically, we propose a novel and efficient algorithm, called randomized Switching for Maximizing Lifetime (RaSMaLai), that aims at extending the lifetime of WSNs through load balancing. Given an initial data collection tree, RaSMaLai randomly switches some sensor nodes from their original paths to other paths with lower load. We prove that, under appropriate settings of the operating parameters, RaSMaLai converges with a low time complexity. We further design a distributed version of our algorithm. Through an extensive performance evaluation study that includes simulation of large-scale scenarios and real experiments on a WSN testbed, we show that the proposed RaSMaLai algorithm and its distributed version achieve a longer network lifetime than the state-of-the-art solutions.

关键词： Data collection tree load balancing network lifetime randomized algorithm wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

randomized renaming in shared memory systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2021年 150卷 112-120页

作者： Berenbrink, Petra Brinkmann, Andre Elsaesser, Robert Friedetzky, Tom Nagel, Lars Univ Hamburg Fachbereich Informat D-22527 Hamburg Germany Johannes Gutenberg Univ Mainz Zentrum Datenverarbeitung D-55099 Mainz Germany Univ Salzburg Dept Comp Sci A-5020 Salzburg Austria Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Loughborough Univ Dept Comp Sci Loughborough LE11 3TU Leics England

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1+ epsilon).n and constant epsilon, they achieve a step complexity of O(log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared-memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1+2/(log n)(l)).n = (1+o(1)).n performing O(l.(log log n)(2)) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(log n), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well. (c) 2021 Elsevier Inc. All rights reserved.

关键词： Tight renaming Loose renaming Distributed algorithm Shared memory model randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized probabilistic approach for parametric uncertainties in unmanned helicopters

引用

OPTIMAL CONTROL APPLICATIONS & METHODS 2021年第2期42卷 376-394页

作者： Singh, Rupam Bhushan, Bharat Delhi Technol Univ Dept Elect Engn Bawana Rd Delhi India

Parametric uncertainties and the problems associated with the design of robust state feedback control tends to be a major concern for achieving stable operation of nonlinear systems. To overcome these drawbacks, this article provides a perspective on a randomized algorithm based probabilistic control for nonlinear systems. The control approach aims at development of randomized algorithms for control of unmanned helicopters which are subjected to uncertainties. A controller gain is synthesized by developing a robust probabilistic approach using sequential randomized algorithm with the two degree of freedom helicopter system. Subsequently, the stability and reachability for the action of developed controller is validated with the help of Lyapunov asymptotic stability and reach tube analysis, and the corresponding results were analyzed. A comparative assessment of simulation and real-time control results of projected approaches on helicopter model are presented for validation of the controller response.

关键词： helicopter system LQR control parametric uncertainty probabilistic control randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A randomized adaptive neighbor discovery for wireless networks with multi-packet reception capability

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年第0期131卷 235-244页

作者： Chae, Sung-Yoon Kang, Kyungran Cho, Young-Jong Korea Railrd Res Inst Control & Commun Res Team Uiwang South Korea Ajou Univ Coll Informat & Technol Suwon South Korea

Neighbor discovery is a first step in the initialization of wireless networks in large-scale ad hoc networks. In this paper, we propose a randomized neighbor discovery scheme for wireless networks with a multi packet reception (MPR) capability. We let the nodes to have different advertisement probabilities. The node gradually adjusts its probability according to its operation phases: greedy or slow-start. In the greedy phase, the node advertises aggressively while it does moderately in the slow-start phase. Initial phase and advertisement probability are determined randomly. Then, the nodes change the probability adaptively according to advertisements the reception state from the other nodes. In order to decide the reception state precisely, the exact number of nodes in the network is necessary. To make our proposed scheme work in case of no prior knowledge of the population, we propose a population estimation method based on a maximum likelihood estimation. We evaluate our proposed scheme through numerical analysis and simulation. Through the numerical analysis, we show that the discovery completion time is lower bounded in Theta(N/k) and upper bounded in Theta(NlnN/k) when there exists N nodes with MPR-k capability. The bounds are the same as those of previous studies that propose static optimal advertisement probability. Through the simulation, we evaluate that our adaptive scheme outperforms in terms of discovery completion time, advertisement efficiency, and wasted time slot ratio than a scheme with static advertisement probability when the population of the network is unknown. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Neighbor discovery Wireless network randomized algorithm Multi-packet reception Maximum likelihood estimation Adaptive advertisement

来源：评论

学校读者我要写书评

暂无评论

Robust Three-Microphone Speech Source Localization Using randomized Singular Value Decomposition

引用

IEEE ACCESS 2021年 9卷 157800-157811页

作者： Tokgoz, Serkan Panahi, Issa M. S. Univ Texas Dallas Dept Elect & Comp Engn Richardson TX 75080 USA

Direction-of-arrival (DOA) estimation is a fundamental technique in array signal processing due to its wide applications in beamforming, speech enhancement and many other assistive speech processing technologies. In this paper, we devise a novel DOA technique based on randomized singular value decomposition (RSVD) to improve the performance of non-uniform non-linear microphone arrays (NUNLA). The accurate and efficient singular value decomposition of large data matrices is computationally challenging, and randomization provides an effective tool for performing matrix approximation, therefore, the developed DOA estimation utilizes a modified dictionary-based RSVD method for localizing single speech sources under low signal-to-noise ratios (SNR). Unlike previous methods developed for uniform linear microphone arrays, the proposed approach with L-shaped three microphone setup has no 'left-right' ambiguity. We present the performance of our proposed method in comparison to other techniques. The demonstrated experiments shows at-least 20% performance improvement using simulated data and 25% performance improvement using real data when compared with similar DoA estimation techniques for NUNLA. The proposed method exploits frame-based online time delay of arrival (TDOA) measurements which facilitates the proposed algorithm to run on real-time devices. We also show an efficient real-time implementation of the proposed method on a Pixel 3 Android smartphone using its built-in three microphones for hearing aid applications.

关键词： Direction-of-arrival estimation Microphone arrays Signal to noise ratio Location awareness Estimation Auditory system Signal processing algorithms Hearing aid device low SNR non-uniform microphone arrays randomized algorithm real-time implementation singular value decomposition smartphone speech source localization

来源：评论

学校读者我要写书评

暂无评论

Distributed Frequency Control in Smart Grids via randomized Demand Response

引用

IEEE TRANSACTIONS ON SMART GRID 2014年第6期5卷 2798-2809页

作者： Moghadam, Mohammad R. Vedady Ma, Richard T. B. Zhang, Rui Natl Univ Singapore Dept Elect & Comp Engn Singapore 117548 Singapore Natl Univ Singapore Dept Comp Sci Singapore 117548 Singapore Adv Digital Sci Ctr Singapore Singapore ASTAR Inst Infocomm Res Singapore Singapore

Frequency control is essential to maintain the stability and reliability of power grids. For decades, generation side controllers, e. g., governors and automatic generation controllers, have been used to stabilize the frequency of power systems, which incur high operational costs. In smart grids, utilizing demand response is an appealing alternative to control the system frequency at the demand side, which can reduce the dependency of grids on expensive generation side controllers. Despite of economic advantages, the frequency oscillation problem, which occurs when smart appliances simultaneously respond to the system frequency by varying their power consumptions, is the main barrier to realize demand response enabled frequency control in practice. In this paper, we investigate a new distributed control algorithm by randomizing smart appliances' responses to solve this problem. We provide a comprehensive analysis to characterize various impacts of the randomized demand response on the system frequency in terms of its mean and variance over time. Furthermore, based on the frequency dynamics analysis, we determine the average frequency recovery time, the average number of responded smart appliances, and the probability of frequency overshoot, which provide important guidelines for designing our control algorithm. Finally, we validate our analysis via simulations under practical setups.

关键词： Demand response distributed frequency control randomized algorithm smart grids

来源：评论

学校读者我要写书评

暂无评论

randomized Dynamic Mode Decomposition

引用

SIAM JOURNAL ON APPLIED DYNAMICAL SYSTEMS 2019年第4期18卷 1867-1891页

作者： Erichson, N. Benjamin Mathelin, Ionel Kutz, J. Nathan Brunton, Steven L. Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA LIMSI CNRS Campus Univ Orsay Orsay 91405 France Univ Washington Dept Appl Math Seattle WA 98195 USA

This paper presents a randomized algorithm for computing the near-optimal low-rank dynamic mode decomposition (DMD). randomized algorithms are emerging techniques to compute low-rank matrix approximations at a fraction of the cost of deterministic algorithms, easing the computational challenges arising in the area of "big data." The idea is to derive a small matrix from the high-dimensional data, which is then used to efficiently compute the dynamic modes and eigenvalues. The algorithm is presented in a modular probabilistic framework, and the approximation quality can be controlled via oversampling and power iterations. The effectiveness of the resulting randomized DMD algorithm is demonstrated on several benchmark examples of increasing complexity, providing an accurate and efficient approach to extract spatiotemporal coherent structures from big data in a framework that scales with the intrinsic rank of the data, rather than the ambient measurement dimension. For this work we assume that the dynamics of the problem under consideration is evolving on a low-dimensional subspace that is well characterized by a quickly decaying singular value spectrum.

关键词： dynamic mode decomposition randomized algorithm dimension reduction dynamical systems

来源：评论

学校读者我要写书评

暂无评论

Kernelization and randomized Parameterized algorithms for Co-path Set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期32卷 67-78页

作者： Feng, Qilong Zhou, Qian Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Hunan Engn Ctr Currency Recognit & Self Serv Changsha 410083 Hunan Peoples R China

Co-path Set problem is of important applications in mapping unique DNA sequences onto chromosomes and whole genomes. Given a graph G, the parameterized version of Co-path Set problem is to find a subset F of edges with size at most k such that each connected component in is a path. In this paper, we give a kernel of size 6k and a randomized algorithm of running time for the Parameterized Co-path Set problem. The randomized methods developed in the paper are of great promising to be applied to other branch-based algorithms.

关键词： Co-path Set Kernelization randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized GENERATION OF ERROR CONTROL CODES WITH AUTOMATA AND TRANSDUCERS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2018年第2-4期52卷 169-184页

作者： Konstantinidis, Stavros Moreira, Nelma Reis, Rogerio St Marys Univ Dept Math & Comp Sci Halifax NS Canada Univ Porto CMUP Fac Ciencias Rua Campo Alegre P-4169007 Porto Portugal Univ Porto DCC Fac Ciencias Rua Campo Alegre P-4169007 Porto Portugal

We introduce the concept of an f-maximal error-detecting block code, for some parameter f in (0,1), in order to formalize the situation where a block code is close to maximal with respect to being error-detecting. Our motivation for this is that it is computationally hard to decide whether an error-detecting block code is maximal. We present an output-polynomial time randomized algorithm that takes as input two positive integers N, l and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length l that is 99%-maximal, or contains N words with a high likelihood. We model error specifications as (nondeterministic) transducers, which allow one to represent any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.

关键词： randomized algorithm output polynomial time algorithm error control codes maximal codes synchronization errors combinatorial channels

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：