Author name cluster

Michele Borassi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

NeurIPS Conference 2020 Conference Paper

Sliding Window Algorithms for k-Clustering Problems

Michele Borassi
Alessandro Epasto
Silvio Lattanzi
Sergei Vassilvitskii
Morteza Zadimoghaddam

The sliding window model of computation captures scenarios in which data is arriving continuously, but only the latest $w$ elements should be used for analysis. The goal is to design algorithms that update the solution efficiently with each arrival rather than recomputing it from scratch. In this work, we focus on $k$-clustering problems such as $k$-means and $k$-median. In this setting, we provide simple and practical algorithms that offer stronger performance guarantees than previous results. Empirically, we show that our methods store only a small fraction of the data, are orders of magnitude faster, and find solutions with costs only slightly higher than those returned by algorithms with access to the full dataset.

PDF Details

SODA Conference 2017 Conference Paper

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

Michele Borassi
Pierluigi Crescenzi
Luca Trevisan 0001

In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is no worst-case guarantee. In this work, we propose an axiomatic framework to analyze the performances of these algorithms, by proving that they are efficient on the class of graphs satisfying certain properties. Furthermore, we prove that these properties are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the Configuration Model, the Chung-Lu model, and the Norros-Reittu model. Thus, our results imply average-case analyses in these models. For example, in our framework, existing algorithms can compute the diameter and the radius of a graph in subquadratic time, and sometimes even in time n 1+o(1). Moreover, in some regimes, it is possible to compute the k most central vertices according to closeness centrality in subquadratic time, and to design a distance oracle with sublinear query time and subquadratic space occupancy. In the worst case, it is impossible to obtain comparable results for any of these problems, unless widely- believed conjectures are false.

Details

TCS Journal 2015 Journal Article

Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

Michele Borassi
Pierluigi Crescenzi
Michel Habib
Walter A. Kosters
Andrea Marino
Frank W. Takes

In this paper, we propose a new algorithm that computes the radius and the diameter of a weakly connected digraph G = ( V, E ), by finding bounds through heuristics and improving them until they are validated. Although the worst-case running time is O ( | V | | E | ), we will experimentally show that it performs much better in the case of real-world networks, finding the radius and diameter values after 10–100 BFSs instead of | V | BFSs (independently of the value of | V | ), and thus having running time O ( | E | ) in practice. As far as we know, this is the first algorithm able to compute the diameter of weakly connected digraphs, apart from the naive algorithm, which runs in time Ω ( | V | | E | ) performing a BFS from each node. In the particular cases of strongly connected directed or connected undirected graphs, we will compare our algorithm with known approaches by performing experiments on a dataset composed by several real-world networks of different kinds. These experiments will show that, despite its generality, the new algorithm outperforms all previous methods, both in the radius and in the diameter computation, both in the directed and in the undirected case, both in average running time and in robustness. Finally, as an application example, we will use the new algorithm to determine the solvability over time of the “Six Degrees of Kevin Bacon” game, and of the “Six Degrees of Wikipedia” game. As a consequence, we will compute for the first time the exact value of the radius and the diameter of the whole Wikipedia digraph.

Details DOI