Search Results

Documents authored by Cruciani, Emilio

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.70
Incremental (k, z)-Clustering on Graphs

Authors: Emilio Cruciani, Sebastian Forster, and Antonis Skarlatos

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Given a weighted undirected graph, a number of clusters k, and an exponent z, the goal in the (k, z)-clustering problem on graphs is to select k vertices as centers that minimize the sum of the distances raised to the power z of each vertex to its closest center. This problem includes the well-known k-median (z = 1) and k-means (z = 2) clustering problems. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact (k, z)-clustering solution in the induced shortest-path metric. Prior works by Bhattacharya, Costa, Garg, Lattanzi, and Parotsidis [FOCS 2024] and by Bhattacharya, Costa, and Farokhnejad [STOC 2025] consider the dynamic (k, z)-clustering problem for point sets in metric spaces. These algorithms support adversarial point insertions and deletions under a model with access to pairwise distances. This model differs significantly from the dynamic graph setting, where no oracle access is given to pairwise distances and a single edge update can affect many distances - making these approaches inefficient when applied to graphs. While efficient dynamic k-center approximation algorithms on graphs exist [Cruciani, Forster, Goranci, Nazari, and Skarlatos, SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic (k,z)-clustering problem. As the main result of this paper, we develop a randomized incremental (k, z)-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of Õ(k m^{1+o(1)} + k^{1+1/(λ)} m), where λ ≥ 1 is an arbitrary fixed constant. Our incremental algorithm also achieves an amortized update time of Õ(k n^o(1) + k^{1+1/(λ)}) and consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size Õ(k) with a total update time of m^{1+o(1)} (independent of the parameter k) over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant - a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate (k,z)-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static (k,z)-clustering algorithm.
Cite as

Emilio Cruciani, Sebastian Forster, and Antonis Skarlatos. Incremental (k, z)-Clustering on Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 70:1-70:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.ICALP.2026.70,
  author =	{Cruciani, Emilio and Forster, Sebastian and Skarlatos, Antonis},
  title =	{{Incremental (k, z)-Clustering on Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{70:1--70:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.70},
  URN =		{urn:nbn:de:0030-drops-264599},
  doi =		{10.4230/LIPIcs.ICALP.2026.70},
  annote =	{Keywords: (k, z)-clustering, k-median, k-means, dynamic graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.14
The Careless Coupon Collector’s Problem

Authors: Emilio Cruciani and Aditi Dudeja

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We initiate the study of the Careless Coupon Collector’s Problem (CCCP), a novel variation of the classical coupon collector, that we envision as a model for information systems such as web crawlers, dynamic caches, and fault-resilient networks. In CCCP, a collector attempts to gather n distinct coupon types by obtaining one coupon type uniformly at random in each discrete round, however the collector is careless: at the end of each round, each collected coupon type is independently lost with probability p. We analyze the number of rounds required to complete the collection as a function of n and p. In particular, we show that it transitions from Θ(n ln n) when p = o((ln n)/n²) up to Θ(((np)/(1-p))ⁿ) when p = ω(1/n) in multiple distinct phases. Interestingly, when p = c/n, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around 1/(1+c) with probability 1-o(1), for a time window of length e^{Θ(n)}. Finally, we give an algorithm that computes the expected completion time of CCCP in O(n²) time.
Cite as

Emilio Cruciani and Aditi Dudeja. The Careless Coupon Collector’s Problem. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.FUN.2026.14,
  author =	{Cruciani, Emilio and Dudeja, Aditi},
  title =	{{The Careless Coupon Collector’s Problem}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.14},
  URN =		{urn:nbn:de:0030-drops-257333},
  doi =		{10.4230/LIPIcs.FUN.2026.14},
  annote =	{Keywords: Coupon Collector, Markov Chains, Metastability}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.26
Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders

Authors: Emilio Cruciani, Sebastian Forster, and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact k of their neighbors instead of a single one during both PUSH and PULL operations. We show that rumor spreading can be made faster at the cost of an increased amount of communication between the nodes. As a motivating example, consider the process on a complete graph of n nodes: while the standard PUSH&PULL protocol takes Θ(log n) rounds, we prove that our k-PUSH&PULL variant completes in Θ(log_{k} n) rounds, with high probability. We generalize this result in an expansion-sensitive way, as has been done for the classic PUSH&PULL protocol for different notions of expansion, e.g., conductance and vertex expansion. We consider small-set vertex expanders, graphs in which every sufficiently small subset of nodes has a large neighborhood, ensuring strong local connectivity. In particular, when the expansion parameter satisfies ϕ > 1, these graphs have a diameter of o(log n), as opposed to other standard notions of expansion. Since the graph’s diameter is a lower bound on the number of rounds required for rumor spreading, this makes small-set expanders particularly well-suited for fast information dissemination. We prove that k-PUSH&PULL takes O(log_{ϕ} n ⋅ log_{k} n) rounds in these expanders, with high probability. We complement this with a simple lower bound of Ω(log_{ϕ} n+ log_{k} n) rounds.
Cite as

Emilio Cruciani, Sebastian Forster, and Tijn de Vos. Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.DISC.2025.26,
  author =	{Cruciani, Emilio and Forster, Sebastian and de Vos, Tijn},
  title =	{{Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{26:1--26:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.26},
  URN =		{urn:nbn:de:0030-drops-248434},
  doi =		{10.4230/LIPIcs.DISC.2025.26},
  annote =	{Keywords: small set expansion, vertex expansion, rumor spreading, multi-call rumor spreading, push\&pull protocol}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.42
Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model

Authors: Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.
Cite as

Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.DISC.2020.42,
  author =	{Cruciani, Emilio and Mimun, Hlafo Alfie and Quattropani, Matteo and Rizzo, Sara},
  title =	{{Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.42},
  URN =		{urn:nbn:de:0030-drops-131200},
  doi =		{10.4230/LIPIcs.DISC.2020.42},
  annote =	{Keywords: Biased Communication, Consensus, Majority Dynamics, Markov Chains, Metastability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.20
Step-By-Step Community Detection in Volume-Regular Graphs

Authors: Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k "stepwise" eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k eigenvalues and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
Cite as

Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-By-Step Community Detection in Volume-Regular Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ISAAC.2019.20,
  author =	{Becchetti, Luca and Cruciani, Emilio and Pasquale, Francesco and Rizzo, Sara},
  title =	{{Step-By-Step Community Detection in Volume-Regular Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.20},
  URN =		{urn:nbn:de:0030-drops-115163},
  doi =		{10.4230/LIPIcs.ISAAC.2019.20},
  annote =	{Keywords: Community detection, Distributed algorithms, Dynamics, Markov chains, Spectral analysis}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact