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

Upper tail analysis of bucket sort and random tries

THEORETICAL COMPUTER SCIENCE 2021年 895卷 55-67页

作者： Bercea, Ioana O. Even, Guy Tel Aviv Univ Tel Aviv Israel

Bucket Sort is known to run in expected linear time when the input keys are distributed independently and uniformly at random in the interval [0,1). The analysis holds even when a quadratic time algorithm is used to sort the keys in each bucket. We show how to obtain linear time guarantees on the running time of Bucket Sort that hold with very high probability. Specifically, we investigate the asymptotic behavior of the exponent in the upper tail probability of the running time of Bucket Sort. We consider large additive deviations from the expectation, of the form cn for large enough (constant) c, where n is the number of keys that are sorted. Our analysis shows a profound difference between variants of Bucket Sort that use a quadratic time algorithm within each bucket and variants that use a Theta(b log b) time algorithm for sorting b keys in a bucket. When a quadratic time algorithm is used to sort the keys in a bucket, the probability that Bucket Sort takes cn more time than expected is exponential in Theta(root n log n). When a Theta(b log b) algorithm is used to sort the keys in a bucket, the exponent becomes Theta(n). We prove this latter theorem by showing an upper bound on the tail of a random variable defined on tries, a result which we believe is of independent interest. This result also enables us to analyze the upper tail probability of a well-studied trie parameter, the external path length, and show that the probability that it deviates from its expected value by an additive factor of cn is exponentially small in Theta(n). (C) 2021 Published by Elsevier B.V.

关键词： Sorting randomized algorithms Analysis of running time

来源：评论

学校读者我要写书评

暂无评论

The randomized 𝑘-Server Conjecture Is False! 2023

The Randomized 𝑘-Server Conjecture Is False!

引用

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Sébastien Bubeck Christian Coester Yuval Rabani Microsoft Research USA University of Oxford UK Hebrew University of Jerusalem Israel

ISBN: (纸本)9781450399135

We prove a few new lower bounds on the randomized competitive ratio for the k-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987). More concretely, we show: (1) There exist (k+1)-point metric spaces in which the randomized competitive ratio for the k-server problem is Ω(log2 k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least k+1 points, the competitive ratio is Θ(logk). (2) Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Ω(log2 n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Ω(logn) (which was known to be tight for some families of metrics). (3) For all krandomized k-server competitive ratio is at least Ω(logk), and consequently the randomized MTS competitive ratio is at least Ω(logn). These universal lower bounds are asymptotically tight. The previous bounds were Ω(logk/loglogk) and Ω(logn/loglogn), respectively. (4) The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Ω(w2). This slightly improves the previous lower bound and matches the recently discovered upper bound. (5) Our results imply improved lower bounds for other problems like k-taxi, distributed paging, and metric allocation. These lower bounds share a common thread, and other than the third bound, also a common construction.

关键词： randomized algorithms metrical task systems online computing competitive analysis $k$-server lower bounds

来源：评论

学校读者我要写书评

暂无评论

A note on the k-restriction problem

引用

Information Processing Letters 2025年 187卷

作者： Lin, Jing-You Tsai, Shi-Chun Department of Computer Science National Yang Ming Chiao Tung University Hsinchu Taiwan

Consider a set of demands, each taking length-k strings as input. The k-restriction problem is to construct a small set of length-m strings, such that given any k positions and any demand, there exists a string in the set satisfying the demand at these positions. The k-restriction problem relates to many problems, such as k-independent sets, covering arrays, and many other combinatorial applications. By considering the VC-dimension of demands, we prove bounds independent of the number of demands with the Lovász Local Lemma. As a result, we can prove better bounds for demands with finite VC-dimension. © 2024 Elsevier B.V.

关键词： randomized algorithms Lovász Local Lemma VC-dimension ϵ-net Probabilistic methods

来源：评论

学校读者我要写书评

暂无评论

Parallel Load Balancing on constrained client-server topologies

引用

THEORETICAL COMPUTER SCIENCE 2021年 895卷 16-33页

作者： Clementi, Andrea Natale, Emanuele Ziccardi, Isabella Univ Roma Tor Vergata Rome Italy Univ Cote Azur INRIA CNRS Sophia Antipolis France Univ Aquila Laquila Italy

We study parallel Load Balancing protocols for the client-server distributed model defined as follows. There is a set C of n clients and a set S of n servers where each client has (at most) a constant number d >= 1 of requests that must be assigned to some server. The client set and the server one are connected to each other via a fixed bipartite graph: the requests of client v can only be sent to the servers in its neighborhood N (v). The goal is to assign every client request so as to minimize the maximum load of the servers. In this setting, efficient parallel protocols are available only for dense topologies. In particular, a simple protocol, named RAES, has been recently introduced by Becchetti et al. [1] for regular dense bipartite graphs. They show that this symmetric, non-adaptive protocol achieves constant maximum load with parallel completion time O(logn) and overall work O(n), w.h.p. Motivated by proximity constraints arising in some client-server systems, we analyze RAES over almost-regular bipartite graphs where nodes may have neighborhoods of small size. In detail, we prove that, w.h.p., the RAES protocol keeps the same performances as above (in terms of maximum load, completion time, and work complexity, respectively) on any almost-regular bipartite graph with degree Omega(log(2) n). Our analysis significantly departs from that in [1] since it requires to cope with non-trivial stochastic-dependence issues on the random choices of the algorithmic process which are due to the worst-case, sparse topology of the underlying graph. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Parallel balanced allocations Balls-into-bins processes randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Query-competitive sorting with uncertainty

引用

THEORETICAL COMPUTER SCIENCE 2021年 867卷 50-67页

作者： Halldorsson, Magnus M. de Lima, Murilo Santos Reykjavik Univ Dept Comp Sci Menntavegi 1 IS-102 Reykjavik Iceland Univ Leicester Sch Informat Univ Rd Leicester LE1 7RH Leics England

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs;for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields the following improved results: (i) a 3/2-query-competitive randomized algorithm;(ii) a 5/3-query competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k;and (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also give a randomized adaptive algorithm with query-competitive factor 1 + 4/3 root 3 approximate to 1.7698 for arbitrary query costs, and we show that the 2-query competitive deterministic adaptive algorithm can be generalized for queries returning intervals and for a more general graph problem (which is also a generalization of the vertex cover problem), by using the local ratio technique. Furthermore, we prove that the advice complexity of the adaptive problem is left perpendicularn/2right perpendicular if no error threshold is allowed, and inverted left perpendicularn/3 lg 3inverted right perpendicular for the general case. Finally, we present some graph-theoretical results regarding co-threshold tolerance grap

关键词： Online algorithms Sorting randomized algorithms Advice complexity Threshold tolerance graphs

来源：评论

学校读者我要写书评

暂无评论

Estimating the Longest Increasing Subsequence in Nearly Optimal Time 63

Estimating the Longest Increasing Subsequence in Nearly Opti...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Andoni, Alexandr Nosatzki, Negev Shekel Sinha, Sandip Stein, Clifford Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781665455190

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time O(n log n), the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS << n, is still open. We show that for any n is an element of N and lambda = o(1), there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS >= lambda n, approximates the LIS up to a factor of 1/lambda(o(1)) in n(o(1))/lambda time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time;and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of Omega(1/lambda), which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from "coarse" (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

关键词： sublinear algorithms approximation algorithms randomized algorithms longest increasing subsequence string algorithms

来源：评论

学校读者我要写书评

暂无评论

Phase Transition of the 3-Majority Dynamics with Uniform Communication Noise 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： d'Amore, Francesco Ziccardi, Isabella Univ Cote Azur INRIA CNRS I3S Sophia Antipolis France Univ Aquila Laquila Italy

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

Communication noise is a common feature in several real-world scenarios where systems of agents need to communicate in order to pursue some collective task. In particular, many biologically inspired systems that try to achieve agreements on some opinion must implement resilient dynamics that are not strongly affected by noisy communications. In this work, we study the popular 3-Majority dynamics, an opinion dynamics which has been proved to be an efficient protocol for the majority consensus problem, in which we introduce a simple feature of uniform communication noise, following (d'Amore et al. 2020). We prove that in the fully connected communication network of n agents and in the binary opinion case, the process induced by the 3-Majority dynamics exhibits a phase transition. For a noise probability p < 1/3, the dynamics reaches in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. Furthermore, departing from previous analyses, we further characterize this phase by showing that there exists an attractive equilibrium value s(eq) is an element of [n] for the bias of the system, i.e. the difference between the majority community size and the minority one. Moreover, the agreement opinion turns out to be the initial majority one if the bias towards it is of magnitude Omega(root n log n) in the initial configuration. If, instead, p > 1/3, no form of consensus is possible, and any information regarding the initial majority opinion is lost in logarithmic time with high probability. Despite more communications per-round are allowed, the 3-Majority dynamics surprisingly turns out to be less resilient to noise than the Undecided-State dynamics (d'Amore et al. 2020), whose noise threshold value is p = 1/2.

关键词： Opinion dynamics Consensus Problem Communication Noise randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Bidirectional stochastic configuration network for regression problems

引用

NEURAL NETWORKS 2021年 140卷 237-246页

作者： Cao, Weipeng Xie, Zhongwu Li, Jianqiang Xu, Zhiwu Ming, Zhong Wang, Xizhao Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China

To adapt to the reality of limited computing resources of various terminal devices in industrial applications, a randomized neural network called stochastic configuration network (SCN), which can conduct effective training without GPU, was proposed. SCN uses a supervisory random mechanism to assign its input weights and hidden biases, which makes it more stable than other randomized algorithms but also leads to time-consuming model training. To alleviate this problem, we propose a novel bidirectional SCN algorithm (BSCN) in this paper, which divides the way of adding hidden nodes into two modes: forward learning and backward learning. In the forward learning mode, BSCN still uses the supervisory mechanism to configure the parameters of the newly added nodes, which is the same as SCN. In the backward learning mode, BSCN calculates the parameters at one time based on the residual error feedback of the current model. The two learning modes are performed iteratively until the prediction error of the model reaches an acceptable level or the number of hidden nodes reaches its maximum value. This semi-random learning mechanism greatly speeds up the training efficiency of the BSCN model and significantly improves the quality of the hidden nodes. Extensive experiments on ten benchmark regression problems, two real-life air pollution prediction problems, and a classical image processing problem show that BSCN can achieve faster training speed, higher stability, and better generalization ability than SCN. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： Stochastic configuration network Random vector functional link network randomized algorithms Neural networks with random weights Constructive neural networks

来源：评论

学校读者我要写书评

暂无评论

Derandomization for Sliding Window algorithms with Strict Correctness*

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 444-461页

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Univ Siegen Holderlinstr 3 D-57076 Siegen Germany

In the sliding window streaming model the goal is to compute an output value that only depends on the lastnsymbols from the data stream. Thereby, only space sublinear in the window sizenshould be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instantt, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called "strict correctness" in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption.

关键词： Streaming algorithms Sliding window algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Model-Free Learning for Massive MIMO Systems: Stochastic Approximation Adjoint Iterative Learning Control

引用

IEEE CONTROL SYSTEMS LETTERS 2021年第6期5卷 1946-1951页

作者： Aarnoudse, Leontine Oomen, Tom Eindhoven Univ Technol Dept Mech Engn Control Syst Technol NL-5600 MB Eindhoven Netherlands

Learning can substantially increase the performance of control systems that perform repeating tasks. The aim of this letter is to develop an efficient iterative learning control algorithm for MIMO systems with a large number of inputs and outputs that does not require model knowledge. The gradient of the control criterion is obtained through dedicated experiments on the system. Using a judiciously selected randomization technique, an unbiased estimate of the gradient is obtained from a single dedicated experiment, resulting in fast convergence of a Robbins-Monro type stochastic gradient descent algorithm. Analysis shows that the approach is superior to earlier deterministic approaches and to related SPSA-type algorithms. The approach is illustrated on a multivariable example.

关键词： Approximation algorithms Stochastic processes Data models Convergence Analytical models Optimization Noise measurement Iterative learning control large-scale systems optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：