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

randomized external-memory algorithms for line segment intersection and other geometric problems

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2001年第3期11卷 305-337页

作者： Crauser, A Ferragina, P Mehlhorn, K Meyer, U Ramos, EA Max Planck Inst Informat D-66123 Saarbrucken Germany

We show that the well-known random incremental construction of Clarkson and Shor(18) can be adapted to provide efficient external-memory algorithms for some geometric problems. In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line segments in the plane with K pairwise intersections, that requires Theta((N)/(B) log(M/B) (N)/(B) + (K)/(B)) expected disk accesses, where M is the size of the available internal memory and B is the size of the block transfer. The approach is sufficiently general to derive algorithms for other geometric problems: 3-d half-space intersections, 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched planar point location;these algorithms require an optimal expected number of disk accesses and are simpler than the ones previously known. The results extend to an external-memory model with multiple disks.

关键词： line segment intersections external memory randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized sparse grid algorithms for multivariate integration on Haar wavelet spaces

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2023年第1期43卷 73-98页

作者： Wnuk, M. Gnewuch, M. Univ Osnabruck Dept Math Albrechtstr 28a D-49076 Osnabruck Germany

The deterministic sparse grid method, also known as Smolyak's method, is a well-established and widely used tool to tackle multivariate approximation problems, and there is a vast literature on it. Much less is known about randomized versions of the sparse grid method. In this paper we analyze randomized sparse grid algorithms, namely randomized sparse grid quadratures for multivariate integration on the D-dimensional unit cube [0, 1)(D). Let d, s is an element of N be such that D = d . s. The s-dimensional building blocks of the sparse grid quadratures are based on stratified sampling for s = 1 and on scrambled (0, m, s)-nets for s >= 2. The spaces of integrands and the error criterion we consider are Haar wavelet spaces with parameter alpha and the randomized error (i.e., the worst case root mean square error), respectively. We prove sharp (i.e., matching) upper and lower bounds for the convergence rates of the Nth minimal errors for all possible combinations of the parameters d and s. Our upper error bounds still hold if we consider as spaces of integrands Sobolev spaces of mixed dominated smoothness with smoothness parameters 1/2 < alpha < 1 instead of Haar wavelet spaces.

关键词： Smolyak algorithm multivariate integration Haar function spaces quasi-Monte Carlo (0,m,s)-nets randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Rapid randomized Pruning for Fast Greedy Distributed algorithms

Rapid Randomized Pruning for Fast Greedy Distributed Algorit...

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Pandit, Saurav Pemmaraju, Sriram V. Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

ISBN: (纸本)9781605588889

We start by defining a pruning process involving sellers on one side and buyers on the other. The goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small cost ratio, i.e., the ratio of the total cost of the selected sellers' products to amount that interested buyers are willing to pay. As modeled here, the pruning process can be used to speed up distributed implementations of greedy algorithms (e.g., for minimum dominating set, facility location, etc). We present a randomized instance of the pruning process that, for any positive k, runs in O(k) communication rounds with O(log N)-sized messages, yielding a cost ratio of O(N-c/k). Here N is the product of the number of sellers and number of buyers and c is a small constant. Using this O(k)-round pruning algorithm as the basis, we derive several simple, greedy, O(k)-round distributed approximation algorithms for AIDS and facility location (both metric and non-metric versions). Our algorithms achieve optimal approximation ratios in polylogarithmic rounds and shave a "logarithmic factor" off the best, known, approximation factor, typically achieved using LP-rounding techniques.

关键词： Distributed algorithms Facility Location Greedy algorithms Minimum Dominating Set Primal-dual algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized Stochastic Approximation algorithms 13

Randomized Stochastic Approximation Algorithms

引用

13th European Control Conference (ECC)

作者： Amelin, Konstantin Granichin, Oleg Granichina, Olga St Petersburg State Univ Dept Math & Mech St Petersburg 198504 Russia Russian Acad Sci Inst Problems Mech Engn Moscow 117901 Russia Herzen State Pedag Univ Russia St Petersburg Russia

ISBN: (纸本)9783952426913

Multidimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging problems of multidimensional optimization, it was suggested to use the randomized algorithms of stochastic approximation with perturbed input which have simple forms and provide consistent estimates of the unknown parameters for observations under "almost arbitrary" noise. They are easily "incorporated" in the design of quantum devices to estimate gradient vector of a multi-variable function.

关键词： Approximation algorithms Approximation methods Computers Convergence Noise Quantum computing Vectors Approximation algorithms Approximation method quantum computing Computers Noise stochastic approximation Converge Quantum devices Gradient vector randomized algorithms Unknown parameter Cloning Vectors

来源：评论

学校读者我要写书评

暂无评论

The Query Complexity of Searching Trees with Permanently Noisy Advice

引用

ACM Transactions on algorithms 2025年第2期21卷 1-30页

作者： Lucas Boczkowski Uriel Feige Amos Korman Yoav Rodeh IRIF CNRS and University of Paris Paris France Weizmann Institute of Science Rehovot Israel University of Haifa Haifa Israel and FILOFOCS CNRS Tel-Aviv Israel ORT Braude College Karmiel Israel

We consider a search problem on trees aiming to find a treasure that an adversary places at one of the nodes. The algorithm can query nodes and extract directional information from them. That is, each node holds a pointer, termed advice, to one of its neighbors. Ideally, this advice points to the neighbor that is closer to the treasure, however, with probability \(q\) this advice points to a uniformly random neighbor. Crucially, the advice is permanent, hence querying the same node again yields the same *** \(\Delta\) denote the maximal degree. Roughly speaking, we show that the expected number of queries incurs a phase transition when \(q\) is about \(1/\sqrt{\Delta}\). In a recent paper, at TALG’21, we showed that if \(q\) is above the threshold then the expected number of queries is polynomial in \(n\). Here, we prove that below the threshold, the expected number of queries is \(\mathcal{O}(\sqrt{\Delta}\log\Delta\cdot\log^{2}n)\), which is tight up to an \(\mathcal{O}(\log n)\) factor when \(\Delta\) is small. We further show that this factor can be reduced to \(\mathcal{O}(\log\log n)\) in the case of regular trees and assuming that \(q0\). In addition, we study the case that the treasure must be found with some given probability. We show that for every fixed \(\varepsilon,\delta>0\), if \(q<1/\Delta^{\varepsilon}\) then there exists a search strategy that with probability \(1-\delta\) finds the treasure using \((\delta^{-1}\log n)^{O(\frac{1}{\varepsilon})}\) queries, whereas \((\delta^{-1}\log n)^{\Omega(\frac{1}{\varepsilon})}\) queries are necessary.

关键词： Search algorithms Fault-tolerance Noisy advice randomized algorithms Trees

来源：评论

学校读者我要写书评

暂无评论

Phase transition of the 3-majority opinion dynamics with noisy interactions

引用

THEORETICAL COMPUTER SCIENCE 2025年 1028卷

作者： d'Amore, Francesco Ziccardi, Isabella Bocconi Univ BIDSA Milan Italy

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. Indeed, many biologically inspired systems that try to achieve agreements on some opinion must implement resilient dynamics, i.e. that are not strongly affected by noisy communications. In this work, we study the 3-MAJORITY dynamics, an opinion dynamics that has been shown 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. (2022). 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 reach in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. We 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, we show that t he agreement opinion is the initial majority one root if the bias towards it is of magnitude Omega(root nlog n) in the initial configuration. If, instead, p > 1/3, we show that 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 being allowed, the 3-MAJORITY dynamics surprisingly turns out to be less resilient to noise than the UNDECIDED-STATE dynamics, whose noise threshold value is p = 1/2.

关键词： Opinion dynamics Consensus problem randomized algorithms Distributed computing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function

引用

algorithms 2025年第3期18卷 140-140页

作者： Schulhof, Noah Sukprasert, Pattara Ruppin, Eytan Khuller, Samir Schaffer, Alejandro A. NCI NIH Canc Data Sci Lab Bethesda MD 20892 USA Northwestern Univ Dept Comp Sci Evanston IL 60201 USA Databricks Inc San Francisco CA 94105 USA

Integer linear programs (ILPs) and mixed integer programs (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high frequencies. This behavior is disadvantageous, as, in fields such as biomedicine, the identification and analysis of distinct optima yields valuable domain-specific insights that inform future research directions. In the present work, we introduce MORSE (Multiple Optima via Random Sampling and careful choice of the parameter Epsilon), a randomized, parallelizable algorithm to efficiently generate multiple optima for ILPs. MORSE maps multiplicative perturbations to the coefficients in an instance's objective function, generating a modified instance that retains an optimum of the original problem. We formalize and prove the above claim in some practical conditions. Furthermore, we prove that for 0/1 selection problems, MORSE finds each distinct optimum with equal probability. We evaluate MORSE using two measures;the number of distinct optima found in r independent runs, and the diversity of the list (with repetitions) of solutions by average pairwise Hamming distance and Shannon entropy. Using these metrics, we provide empirical results demonstrating that MORSE outperforms the Gurobi method and unweighted variations of the MORSE method on a set of 20 Mixed Integer Programming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.

关键词： integer linear program selection problems multiple optima randomized algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards a Theory of randomized Shared Memory algorithms 19

Towards a Theory of Randomized Shared Memory Algorithms

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Woelfel, Philipp Univ Calgary Calgary AB Canada

ISBN: (纸本)9781450362177

Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms. For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that. To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomize

关键词： randomized algorithms shared memory concurrency strong linearizability correctness condition mutual exclusion Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2021年 440卷 110391-110391页

作者： Saibaba, Arvind K. Prasad, Pranjal de Sturler, Eric Miller, Eric Kilmer, Misha E. North Carolina State Univ Dept Math Raleigh NC 27513 USA Virginia Tech Dept Math Blacksburg VA 24061 USA Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA Tufts Univ Dept Math Medford MA 02155 USA

Markov chain Monte Carlo (MCMC) approaches are traditionally used for uncertainty quantification in inverse problems where the physics of the underlying sensor modality is described by a partial differential equation (PDE). However, the use of MCMC algorithms is prohibitively expensive in applications where each log-likelihood evaluation may require hundreds to thousands of PDE solves corresponding to multiple sensors;i.e., spatially distributed sources and receivers perhaps operating at different frequencies or wavelengths depending on the precise application. We show how to mitigate the computational cost of each log-likelihood evaluation by using several randomized techniques and embed these randomized approximations within MCMC algorithms. The resulting MCMC algorithms are computationally efficient methods for quantifying the uncertainty associated with the reconstructed parameters. We demonstrate the accuracy and computational benefits of our proposed algorithms on a model application from diffuse optical tomography where we invert for the spatial distribution of optical absorption. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Inverse problems randomized algorithms Bayesian methods Markov chain Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：