3 Search Results for "Roytman, Alan"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.13
Optimal Online Bipartite Matching in Degree-2 Graphs

Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.
Cite as

Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha. Optimal Online Bipartite Matching in Degree-2 Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ISAAC.2025.13,
  author =	{Bhangale, Amey and Chakraborty, Arghya and Harsha, Prahladh},
  title =	{{Optimal Online Bipartite Matching in Degree-2 Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13},
  URN =		{urn:nbn:de:0030-drops-249216},
  doi =		{10.4230/LIPIcs.ISAAC.2025.13},
  annote =	{Keywords: Online Algorithm, Bipartite matching}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.25
Approximating Subadditive Hadamard Functions on Implicit Matrices

Authors: Vladimir Braverman, Alan Roytman, and Gregory Vorsanger

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
An important challenge in the streaming model is to maintain small-space approximations of entrywise functions performed on a matrix that is generated by the outer product of two vectors given as a stream. In other works, streams typically define matrices in a standard way via a sequence of updates, as in the work of Woodruff [22] and others. We describe the matrix formed by the outer product, and other matrices that do not fall into this category, as implicit matrices. As such, we consider the general problem of computing over such implicit matrices with Hadamard functions, which are functions applied entrywise on a matrix. In this paper, we apply this generalization to provide new techniques for identifying independence between two data streams. The previous state of the art algorithm of Braverman and Ostrovsky [9] gave a (1 +- epsilon)-approximation for the L_1 distance between the joint and product of the marginal distributions, using space O(log^{1024}(nm) epsilon^{-1024}), where m is the length of the stream and n denotes the size of the universe from which stream elements are drawn. Our general techniques include the L_1 distance as a special case, and we give an improved space bound of O(log^{12}(n) log^{2}({nm}/epsilon) epsilon^{-7}).
Cite as

Vladimir Braverman, Alan Roytman, and Gregory Vorsanger. Approximating Subadditive Hadamard Functions on Implicit Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2016.25,
  author =	{Braverman, Vladimir and Roytman, Alan and Vorsanger, Gregory},
  title =	{{Approximating Subadditive Hadamard Functions on Implicit Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.25},
  URN =		{urn:nbn:de:0030-drops-66483},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.25},
  annote =	{Keywords: Streaming Algorithms, Measuring Independence, Hadamard Functions, Implicit Matrices}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.573
Zero-One Laws for Sliding Windows and Universal Sketches

Authors: Vladimir Braverman, Rafail Ostrovsky, and Alan Roytman

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
Given a stream of data, a typical approach in streaming algorithms is to design a sophisticated algorithm with small memory that computes a specific statistic over the streaming data. Usually, if one wants to compute a different statistic after the stream is gone, it is impossible. But what if we want to compute a different statistic after the fact? In this paper, we consider the following fascinating possibility: can we collect some small amount of specific data during the stream that is "universal," i.e., where we do not know anything about the statistics we will want to later compute, other than the guarantee that had we known the statistic ahead of time, it would have been possible to do so with small memory? This is indeed what we introduce (and show) in this paper with matching upper and lower bounds: we show that it is possible to collect universal statistics of polylogarithmic size, and prove that these universal statistics allow us after the fact to compute all other statistics that are computable with similar amounts of memory. We show that this is indeed possible, both for the standard unbounded streaming model and the sliding window streaming model.
Cite as

Vladimir Braverman, Rafail Ostrovsky, and Alan Roytman. Zero-One Laws for Sliding Windows and Universal Sketches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 573-590, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2015.573,
  author =	{Braverman, Vladimir and Ostrovsky, Rafail and Roytman, Alan},
  title =	{{Zero-One Laws for Sliding Windows and Universal Sketches}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{573--590},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.573},
  URN =		{urn:nbn:de:0030-drops-53248},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.573},
  annote =	{Keywords: Streaming Algorithms, Universality, Sliding Windows}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2016
  • 1 2015

  • Refine by Author
  • 2 Braverman, Vladimir
  • 2 Roytman, Alan
  • 1 Bhangale, Amey
  • 1 Chakraborty, Arghya
  • 1 Harsha, Prahladh
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 2 Streaming Algorithms
  • 1 Bipartite matching
  • 1 Hadamard Functions
  • 1 Implicit Matrices
  • 1 Measuring Independence
  • 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