Zobrazeno 1 - 10
of 43
pro vyhledávání: '"Scquizzato, Michele"'
Autor:
Peserico, Enoch, Scquizzato, Michele
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least $\sqrt{\log_2(n\!+\!1)}/12$ for all $n=2^i\!-\!1: i\in\mathbb{N}$.
Externí odkaz:
http://arxiv.org/abs/2012.15593
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical gr
Externí odkaz:
http://arxiv.org/abs/2001.02191
Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication complexity of computations. This paper presents a lower bound techniqu
Externí odkaz:
http://arxiv.org/abs/1707.02229
This paper presents a randomized Las Vegas distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{
Externí odkaz:
http://arxiv.org/abs/1607.06883
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly
Externí odkaz:
http://arxiv.org/abs/1602.08481
Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines j
Externí odkaz:
http://arxiv.org/abs/1503.02353
Autor:
Bilardi, Gianfranco, Pietracaprina, Andrea, Pucci, Geppino, Scquizzato, Michele, Silvestri, Francesco
A framework is proposed for the design and analysis of \emph{network-oblivious algorithms}, namely, algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capab
Externí odkaz:
http://arxiv.org/abs/1404.3318
Autor:
Hourani, Khalid, Klauck, Hartmut, Moses Jr., William K., Nanongkai, Danupon, Pandurangan, Gopal, Robinson, Peter, Scquizzato, Michele
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, called $k$-machine model, where we have $k$ machines that jointly perfor
Externí odkaz:
http://arxiv.org/abs/1311.6209
We give lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Tran
Externí odkaz:
http://arxiv.org/abs/1307.1805
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.