Search Results

Documents authored by Yan, Shuyi

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.48
Static to Dynamic Correlation Clustering

Authors: Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang

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

Abstract
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear 1.485-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25] , we get an 1.485-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is an 1.485-approximation with constant probability when we reach this update. Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around 3 in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] handles an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.
Cite as

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Static to Dynamic Correlation Clustering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 48:1-48:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICALP.2026.48,
  author =	{Cao, Nairen and Cohen-Addad, Vincent and Lee, Euiwoong and Li, Shi and Lolck, David Rasmussen and Newman, Alantha and Thorup, Mikkel and Vogl, Lukas and Yan, Shuyi and Zhang, Hanwen},
  title =	{{Static to Dynamic Correlation Clustering}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{48:1--48:23},
  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.48},
  URN =		{urn:nbn:de:0030-drops-264378},
  doi =		{10.4230/LIPIcs.ICALP.2026.48},
  annote =	{Keywords: Dynamic Algorithms, Correlation Clustering, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.156
Edge-Weighted Online Stochastic Matching Under Jaillet-Lu LP

Authors: Shuyi Yan

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

Abstract
The online stochastic matching problem was introduced by [Feldman et al., 2009], together with the (1-1/e)-competitive Suggested Matching algorithm. In the most general edge-weighted setting, this ratio has not been improved for more than one decade, until recently [Yan, 2024] beat the 1-1/e bound and [Qiu et al., 2023] further improved it to 0.650. Both works measure the online competitiveness against the offline LP relaxation introduced by Jaillet and Lu [Jaillet and Lu, 2014]. The same LP has also played an important role in other settings as it is a natural choice for two-choice online algorithms. In this paper, we prove an upper bound of 0.663 and a lower bound of 0.662 for edge-weighted online stochastic matching under Jaillet-Lu LP. We propose a simple hard instance and identify the optimal online algorithm for this specific instance which has a competitive ratio of < 0.663. Despite the simplicity of the instance, we then show that a near-optimal algorithm for it, which has a competitive ratio of > 0.662, can be generalized to work on all instances without any loss. As our algorithm is generalized from a real near-optimal algorithm instead of manually combining trivial strategies, it has two natural advantages compared with previous works: (1) its matching strategy varies from time to time; (2) it utilizes global information about offline vertices. On the other hand, the upper bound suggests that more powerful LPs and multiple-choice strategies are needed if we want to further improve the ratio by > 0.001. In addition to our main result, we also generalize the asymptotic equivalence between the Poisson arrival model and the original online stochastic matching established by [Huang and Shu, 2021], removing the requirement of approximate monotonicity for the online algorithm.
Cite as

Shuyi Yan. Edge-Weighted Online Stochastic Matching Under Jaillet-Lu LP. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 156:1-156:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yan:LIPIcs.ICALP.2026.156,
  author =	{Yan, Shuyi},
  title =	{{Edge-Weighted Online Stochastic Matching Under Jaillet-Lu LP}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{156:1--156:18},
  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.156},
  URN =		{urn:nbn:de:0030-drops-265450},
  doi =		{10.4230/LIPIcs.ICALP.2026.156},
  annote =	{Keywords: Online stochastic matching}
}
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