Vladislav Haralampiev · Serdica Journal of Computing · 2019
Finding the 3-edge connected components of a graph is a well-researched problem for which many algorithms are known. In this paper, we present a new linear-time randomized algorithm for the problem. To the best of our knowledge, this is the first randomized algorithm for partitioning a graph into 3-edge connected components. The algorithm is a composition of simple building blocks, it is easy to understand and implement, and it has no corner cases.
Cited by 0Open access
Nikhil Bansal, Niv Buchbinder, Joseph Naor · 2007
In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k) -competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitiveness matches the known lower bound on the problem. More generally, we design an O(log(k/(k - h + I)))-competitive online algorithm for the version of the. problem where, the online algorithm has-cache size k and the online algorithm has cache size h les k. Weighted paging is a special case (weighted star metric) of the well known k-server problem for which it is a major open question whether randomization can be useful in obtaining sub-linear competitive algorithms. Therefore, abstracting and extending the insights from paging is a key step in the resolution of the k-server problem. Our solution for the weighted paging problem is based on a two-step approach. In the first step we obtain an O(log k)-competitive fractional algorithm which is based on a novel online primal-dual approach. In the second step we. obtain a randomized algorithm by rounding online the fractional solution to an actual distribution on integral cache, solutions. We conclude with a randomized O(log N)-competitive algorithm for the well studied Metrical Task System problem (MTS) on a metric defined by a weighted star on N leaves, improving upon a previous O(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N)-competitive algorithm of Blum et al. [9].
Cited by 24
Lucie Pansart, Hadrien Cambazard, Nicolas Catusse · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
International audience
Cited by 0Open access
Tianyu Zuo, Xueyan Tang, Bu‐Sung Lee · 2024
In this paper, we study an online cost optimization problem for distributed data access. The goal of this problem is to dynamically create and delete data copies in a multi-server distributed system as time goes, in order to minimize the total storage and network cost of serving access requests. We propose an online algorithm with randomized storage periods of data copies in the servers, and derive an optimal probability density function of storage periods, which makes the algorithm achieve a competitive ratio of $1 + \frac{{\sqrt 2 }}{2}$. An example is presented to show that the competitive analysis of our algorithm is tight. Experimental evaluations using real data access traces demonstrate that our algorithm outperforms the best known deterministic algorithm.
Cited by 1
Abdushukurova G.Z. · Ġylym men densaulyķ saķtau. · 2015
Cited by 0Open access
Per‐Gunnar Martinsson, Vladimir Rokhlin, Mark Tygert · 2006
Cited by 14
Frasca P., Hendrickx J.M. · PORTO Publications Open Repository TOrino (Politecnico di Torino) · 2012
Cited by 0
Mounir Gouiouez, Noureddine Raïs, Mostafa Azzouzi Idrissi · International Journal of Computer Science and Information Technology · 2013
We present a new Following Car Algorithm in Microscopic Urban Traffic Models which integrates some real-life factors that need to be considered, such as the effect of random distributions in the car speed, acceleration, entry of lane Our architecture is based on Multi-Agent Randomized Systems (MARS) developed in earlier publications.
Cited by 2Open access
Lucie Pansart, Hadrien Cambazard, Nicolas Catusse · Frontiers in artificial intelligence and applications · 2020
The color coding technique is used to solve subgraph isomorphism problems, in particular path problems. One color among C is randomly assigned to each vertex of the graph and if distinct colors are given to the vertices of the desired subgraph, it can be found efficiently by dynamic programming. These two phases are repeated until the subgraph is found with a high probability, which can require a large number of iterations. We propose new coloring strategies that take advantage of the graph structure to increase this probability and thus reduce the number of iterations. They provide a guaranteed improvement over the original color coding technique based on a particular structural parameter related to the bandwidth. When this parameter is smaller than the number C of colors, we prove that only C calls to the dynamic program are needed to find the subgraph.
Cited by 0
Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu · Theory of Computing Systems · 2012
Cited by 7
Alexandros V. Gerbessiotis, Constantinos J. Siniolakis · Discrete Mathematics Algorithms and Applications · 2014
An oversampling-based randomized algorithm is introduced for sorting n keys of any abstract data type on the p processors of a latency-tolerant parallel system such as a bulk-synchronous parallel computer. The algorithm is asymptotically, for large n, optimal in computation and communication compared to the best available sequential sorting algorithm, even when constant factors are taken into consideration. Its parallel time is within a (1 + o(1))/p multiplicative factor of the corresponding sequential method for sorting, improving upon other approaches for a wider range of values of p relative to n. It also improves upon other randomized sorting algorithms that have been developed for latency-tolerant models of computation on the amount of parallel slack (ratio n over p) required to achieve optimal speedup and also, on the associated failure probability. For values of p closer to n than other latency-tolerant randomized approaches, it can be turned into a PRAM-like algorithm but for such cases a speedup of O(p) rather than p/(1 + o(1)) is then achievable. Although the general framework of the proposed algorithm relies on the well-established prior idea of sample-based sorting, there are some novel features in its design such as the choice of splitter size, the way keys are split, and the handling of the base case of the recursive sorting algorithm that contribute to its performance.
Cited by 0
Matthias Poloczek, Georg Schnitger · 2011
We give a randomized variant of Johnson's algorithm for MAX SAT [12] and show that its expected approximation ratio is ¾. Our solution also works in an online setting where variables are revealed one by one together with the clauses they appear in. Our simple algorithm does not use the power of linear programming and, to the best of our knowledge, is the first such algorithm to reach approximation ratio ¾. We also investigate a variant of Johnson's algorithm proposed in [5] that processes variables in random order. Here we show that the expected approximation ratio is worse than ¾, thus providing a partial answer to a question of [5].
Cited by 10
Connelly Barnes, Dan B Goldman, Eli Shechtman et al. · Communications of the ACM · 2011
This paper presents a new randomized algorithm for quickly finding approximate nearest neighbor matches between image patches. Our algorithm offers substantial performance improvements over the previous state of the art (20--100×), enabling its use in new interactive image editing tools, computer vision, and video applications. Previously, the cost of computing such matches for an entire image had eluded efforts to provide interactive performance. The key insight driving our algorithm is that the elements of our search domain---patches of image pixels---are correlated, and thus the search strategy takes advantage of these statistics. Our algorithm uses two principles: first, that good patch matches can be found via random sampling, and second, that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. Our simple algorithm allows finding a single nearest neighbor match across translations only, whereas our general algorithm additionally allows matching of k -nearest neighbors, across all rotations and scales, and matching arbitrary descriptors. This one simple algorithm forms the basis for a variety of applications including image retargeting, completion, reshuffling, object detection, digital forgery detection, and video summarization.
Cited by 55
Artem Burkov, I. A. Pastushok, Andrey Turlikov · Problems of Information Transmission · 2025
Among known random multiple access (RMA) algorithms, the part-and-try (splitting) algorithm demonstrates the highest throughput. However, its implementation in cellular random access channels is challenging, since the correct operation of the algorithm requires absolute time synchronization among all users to uniquely identify events in a Poisson arrival process. In this paper, we propose a modified RMA algorithm based on the principles of the part-and-try algorithm, in which the introduction of randomization eliminates the need for temporal event identification. This modification enables the algorithm to be implemented in practical random access systems. The achieved throughput of the algorithm is $0.485$ .
Cited by 0
Uriel Feige · Theoretical Computer Science · 1996
Cited by 26
Rui Ye, Qun Dai · Neural Processing Letters · 2017
Cited by 7
Bala Kalyanasundaram, Kirk Pruhs, Clifford Stein · Operations Research Letters · 2023
Cited by 0
Hillel Gazit, John H. Reif · 1990
Article A randomized parallel algorithm for planar graph isomorphism Share on Authors: H. Gazit Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , J. Reif Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 210–219https://doi.org/10.1145/97444.97687Online:01 May 1990Publication History 4citation468DownloadsMetricsTotal Citations4Total Downloads468Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Cited by 16
Haoze He, Daniel Kreßner · CALCOLO · 2025
We present and analyze a simple numerical method that diagonalizes a complex normal matrix <i>A</i> by diagonalizing the Hermitian matrix obtained from a random linear combination of the Hermitian and skew-Hermitian parts of <i>A</i>.
Cited by 0Open access
Sofiia Shvaiko, Longxiu Huang, Elizaveta Rebrova · arXiv (Cornell University) · 2026
Randomized Kaczmarz (RK) is a simple and fast solver for consistent overdetermined systems, but it is known to be fragile under noise. We study overdetermined $m\times n$ linear systems with a sparse set of corrupted equations, $ {\bf A}{\bf x}^\star = {\bf b}, $where only $\tilde{\bf b} = {\bf b} + \boldsymbol{\varepsilon}$ is observed with $\|\boldsymbol{\varepsilon}\|_0 \le βm$. The recently introduced QuantileRK (QRK) algorithm addresses this issue by testing residuals against a quantile threshold, but computing a per-iteration quantile across many rows is costly. In this work we (i) reanalyze QRK and show that its convergence rate improves monotonically as the corruption fraction $β$ decreases; (ii) propose a simple online detector that flags and removes unreliable rows, which reduces the effective $β$ and speeds up convergence; and (iii) make the method practical by estimating quantiles from a small random subsample of rows, preserving robustness while lowering the per-iteration cost. Simulations on imaging and synthetic data demonstrate the efficiency of the proposed method.
Cited by 0Open access