5 Search Results for "Jin, Shendan"

Document
DOI: 10.4230/LIPIcs.SEA.2026.26
Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.
Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.44
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

Authors: Yinhao Dong, Pan Peng, and Ali Vakilian

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a 1/2-approximation for estimating the value of MAX-CUT can be trivially achieved with O(1) words of space, Kapralov and Krachun [STOC’19] showed that this is essentially the best possible: for any ε > 0, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least 1/2 + ε requires Ω(n / 2^poly(1/ε)) space. We show that it is possible to surpass the 1/2-approximation barrier using just O(1) words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an ε-accurate oracle that for each vertex in the graph, returns its correct label in {-1, +1}, corresponding to an optimal MAX-CUT solution in the graph, with some probability 1/2 + ε, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of 1/2 + Ω(ε²) with probability at least 2/3 for insertion-only streams, using only poly(1/ε) words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of poly(1/ε,log n) words.
Cite as

Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-Augmented Streaming Algorithms for Approximating MAX-CUT. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 44:1-44:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dong_et_al:LIPIcs.ITCS.2025.44,
  author =	{Dong, Yinhao and Peng, Pan and Vakilian, Ali},
  title =	{{Learning-Augmented Streaming Algorithms for Approximating MAX-CUT}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{44:1--44:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.44},
  URN =		{urn:nbn:de:0030-drops-226728},
  doi =		{10.4230/LIPIcs.ITCS.2025.44},
  annote =	{Keywords: Learning-Augmented Algorithms, Graph Streaming Algorithms, MAX-CUT}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.52
Online Computation with Untrusted Advice

Authors: Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. This paradigm allows to establish tradeoffs between the amount of this additional information and the performance of the online algorithm. However, unlike real life in which advice is a recommendation that we can choose to follow or to ignore based on trustworthiness, in the current advice model, the online algorithm treats it as infallible. This means that if the advice is corrupt or, worse, if it comes from a malicious source, the algorithm may perform poorly. In this work, we study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust and perform well even when the advice is generated in a malicious, adversarial manner. To this end, we focus on well- studied online problems such as ski rental, online bidding, bin packing, and list update. For ski-rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved; this improves upon the framework of Purohit et al. [NeurIPS 2018] in which Pareto-optimality is not necessarily guaranteed. For bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or not; this is motivated by work of Lykouris and Vassilvitskii [ICML 2018] on the paging problem, but in which the competitiveness depends on the reliability of the advice. Furthermore, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm. Last, we study the effect of randomization: here we show that for ski-rental there is a randomized algorithm that Pareto-dominates any deterministic algorithm with advice of any size. We also show that a single random bit is not always inferior to a single advice bit, as it happens in the standard model.
Cite as

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.ITCS.2020.52,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Jin, Shendan and Kamali, Shahin and Renault, Marc},
  title =	{{Online Computation with Untrusted Advice}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.52},
  URN =		{urn:nbn:de:0030-drops-117372},
  doi =		{10.4230/LIPIcs.ITCS.2020.52},
  annote =	{Keywords: Online computation, competitive analysis, advice complexity, robust algorithms, untrusted advice}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.7
Best-Of-Two-Worlds Analysis of Online Search

Authors: Spyros Angelopoulos, Christoph Dürr, and Shendan Jin

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line nature, in that the input is unknown to the searcher, and the performance of a search strategy is usually analyzed by means of the standard framework of the competitive ratio, which compares the cost incurred by the searcher to an optimal strategy that knows the location of the target. However, one can argue that even for simple search problems, competitive analysis fails to distinguish between strategies which, intuitively, should have different performance in practice. Motivated by the above, in this work we introduce and study measures supplementary to competitive analysis in the context of search problems. In particular, we focus on the well-known problem of linear search, informally known as the cow-path problem, for which there is an infinite number of strategies that achieve an optimal competitive ratio equal to 9. We propose a measure that reflects the rate at which the line is being explored by the searcher, and which can be seen as an extension of the bijective ratio over an uncountable set of requests. Using this measure we show that a natural strategy that explores the line aggressively is optimal among all 9-competitive strategies. This provides, in particular, a strict separation from the competitively optimal doubling strategy, which is much more conservative in terms of exploration. We also provide evidence that this aggressiveness is requisite for optimality, by showing that any optimal strategy must mimic the aggressive strategy in its first few explorations.
Cite as

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Best-Of-Two-Worlds Analysis of Online Search. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.STACS.2019.7,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Jin, Shendan},
  title =	{{Best-Of-Two-Worlds Analysis of Online Search}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.7},
  URN =		{urn:nbn:de:0030-drops-102467},
  doi =		{10.4230/LIPIcs.STACS.2019.7},
  annote =	{Keywords: Online computation, search problems, linear search, performance measures}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.8
Online Maximum Matching with Recourse

Authors: Spyros Angelopoulos, Christoph Dürr, and Shendan Jin

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Avitabile et al., 2013], whereas the special case k=2 was studied by Boyar et al. [Boyar et al., 2017]. In the first part of this paper, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [Avitabile et al., 2013], by exploiting the structure of the matching problem. In addition, we extend the result of [Boyar et al., 2017] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm of [Avitabile et al., 2013]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k-1) exists, improving upon the lower bound of 1+1/k shown in [Avitabile et al., 2013]. The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of (k^2-3k+6)/(k^2-4k+7) for all even k >= 4. For k in {2,3}, the competitive ratio is 3/2.
Cite as

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.MFCS.2018.8,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Jin, Shendan},
  title =	{{Online Maximum Matching with Recourse}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.8},
  URN =		{urn:nbn:de:0030-drops-95908},
  doi =		{10.4230/LIPIcs.MFCS.2018.8},
  annote =	{Keywords: Competitive ratio, maximum cardinality matching, recourse}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2020
  • 1 2019
  • 1 2018

  • Refine by Author
  • 3 Angelopoulos, Spyros
  • 3 Dürr, Christoph
  • 3 Jin, Shendan
  • 1 Dong, Yinhao
  • 1 Kamali, Shahin
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Online algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 Online computation
  • 2 recourse
  • 1 Competitive ratio
  • 1 Dynamic graphs
  • 1 Graph Streaming Algorithms
  • Show More...

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