21 Search Results for "Bernstein, Aaron"


Document
Position
Grounding Stream Reasoning Research

Authors: Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1


Abstract
In the last decade, there has been a growing interest in applying AI technologies to implement complex data analytics over data streams. To this end, researchers in various fields have been organising a yearly event called the "Stream Reasoning Workshop" to share perspectives, challenges, and experiences around this topic. In this paper, the previous organisers of the workshops and other community members provide a summary of the main research results that have been discussed during the first six editions of the event. These results can be categorised into four main research areas: The first is concerned with the technological challenges related to handling large data streams. The second area aims at adapting and extending existing semantic technologies to data streams. The third and fourth areas focus on how to implement reasoning techniques, either considering deductive or inductive techniques, to extract new and valuable knowledge from the data in the stream. This summary is written not only to provide a crystallisation of the field, but also to point out distinctive traits of the stream reasoning community. Moreover, it also provides a foundation for future research by enumerating a list of use cases and open challenges, to stimulate others to join this exciting research area.

Cite as

Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer. Grounding Stream Reasoning Research. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 2:1-2:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{bonte_et_al:TGDK.2.1.2,
  author =	{Bonte, Pieter and Calbimonte, Jean-Paul and de Leng, Daniel and Dell'Aglio, Daniele and Della Valle, Emanuele and Eiter, Thomas and Giannini, Federico and Heintz, Fredrik and Schekotihin, Konstantin and Le-Phuoc, Danh and Mileo, Alessandra and Schneider, Patrik and Tommasini, Riccardo and Urbani, Jacopo and Ziffer, Giacomo},
  title =	{{Grounding Stream Reasoning Research}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{2:1--2:47},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.2},
  URN =		{urn:nbn:de:0030-drops-198597},
  doi =		{10.4230/TGDK.2.1.2},
  annote =	{Keywords: Stream Reasoning, Stream Processing, RDF streams, Streaming Linked Data, Continuous query processing, Temporal Logics, High-performance computing, Databases}
}
Document
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?

Authors: Aaron Bernstein, Greg Bodwin, and Nicole Wein

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
The aspect ratio of a (positively) weighted graph G is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: - Every weighted DAG on n nodes has a shortest-paths preserving graph of aspect ratio O(n). A simple lower bound shows that this is tight. - The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected n-node graphs for which any shortest-paths preserving graph has aspect ratio 2^{Ω(n)}. We also consider the approximate version of this problem, where the goal is for shortest paths in H to correspond to approximate shortest paths in G. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in H must also correspond to approximate shortest paths in G, even DAGs require exponential aspect ratio.

Cite as

Aaron Bernstein, Greg Bodwin, and Nicole Wein. Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.ITCS.2024.12,
  author =	{Bernstein, Aaron and Bodwin, Greg and Wein, Nicole},
  title =	{{Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.12},
  URN =		{urn:nbn:de:0030-drops-195405},
  doi =		{10.4230/LIPIcs.ITCS.2024.12},
  annote =	{Keywords: shortest paths, graph theory, weighted graphs}
}
Document
Dynamic Graph Algorithms (Dagstuhl Seminar 22461)

Authors: Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, and Nicole Wein

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22461 “Dynamic Graph Algorithms”, which took place from November 13 to November 18, 2022. The field of dynamic graph algorithms studies algorithms for processing graphs that are changing over time. Formally, the goal is to process an interleaved sequence of update and query operations, where an update operation changes the input graph (e.g. inserts/deletes an edge), while the query operation is problem-specific and asks for some information about the current graph – for example, an s-t path, or a minimum spanning tree. The field has evolved rapidly over the past decade, and this Dagstuhl Seminar brought together leading researchers in dynamic algorithms and related areas of graph algorithms.

Cite as

Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, and Nicole Wein. Dynamic Graph Algorithms (Dagstuhl Seminar 22461). In Dagstuhl Reports, Volume 12, Issue 11, pp. 45-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{bernstein_et_al:DagRep.12.11.45,
  author =	{Bernstein, Aaron and Chechik, Shiri and Forster, Sebastian and Kopelowitz, Tsvi and Nazari, Yasamin and Wein, Nicole},
  title =	{{Dynamic Graph Algorithms (Dagstuhl Seminar 22461)}},
  pages =	{45--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Bernstein, Aaron and Chechik, Shiri and Forster, Sebastian and Kopelowitz, Tsvi and Nazari, Yasamin and Wein, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.45},
  URN =		{urn:nbn:de:0030-drops-178354},
  doi =		{10.4230/DagRep.12.11.45},
  annote =	{Keywords: dynamic graphs, graph algorithms}
}
Document
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

Authors: Sepehr Assadi, Aaron Bernstein, and Zachary Langley

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
In the weighted load balancing problem, the input is an n-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the 𝓁_∞- or 𝓁₂-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all 𝓁_p-norm objectives for p ≥ 1, including p = ∞, simultaneously. Our main result is a deterministic O(log n)-pass O(1)-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an O(log n)-pass O(log n)-approximation algorithm for the 𝓁_∞-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.

Cite as

Sepehr Assadi, Aaron Bernstein, and Zachary Langley. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ITCS.2023.7,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary},
  title =	{{All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-175106},
  doi =		{10.4230/LIPIcs.ITCS.2023.7},
  annote =	{Keywords: Load Balancing, Semi-Streaming Algorithms, Semi-Matching}
}
Document
Maximum Weight b-Matchings in Random-Order Streams

Authors: Chien-Chung Huang and François Sellier

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We consider the maximum weight b-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from [1,W], we present a 2 - 1/(2W) + ε approximation algorithm, using a memory of O(max(|M_G|, n) ⋅ poly(log(m),W,1/ε)), where |M_G| denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Aaron Bernstein, 2020], which achieves a 3/2 + ε approximation for the maximum cardinality simple matching. When W is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a 2 - δ approximation (for some small constant δ ∼ 10^{-17}) for the maximum weight simple matching. In particular, for the weighted b-matching problem, ours is the first result beating the approximation ratio of 2. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Aaron Bernstein and Cliff Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a 2 - 1/(2W) + ε approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry’s duality theorem.

Cite as

Chien-Chung Huang and François Sellier. Maximum Weight b-Matchings in Random-Order Streams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ESA.2022.68,
  author =	{Huang, Chien-Chung and Sellier, Fran\c{c}ois},
  title =	{{Maximum Weight b-Matchings in Random-Order Streams}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.68},
  URN =		{urn:nbn:de:0030-drops-170062},
  doi =		{10.4230/LIPIcs.ESA.2022.68},
  annote =	{Keywords: Maximum weight matching, b-matching, streaming, random order}
}
Document
Track A: Algorithms, Complexity and Games
Decremental Matching in General Graphs

Authors: Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1+ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [Manoj Gupta and Richard Peng, 2013]) gave an algorithm for this problem with an update time of O(√m/ε²). Motivated by the fact that the O_ε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [Henzinger et al., 2015]; Kopelowitz, Pettie, and Porat [Kopelowitz et al., 2016]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [Bernstein et al., 2020]) gave an O(poly({log n}/ε)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs. In this paper, we bridge the gap between bipartite and general graphs, by giving an O_ε(poly(log n)) update time algorithm that maintains a (1+ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [Fabrizio Grandoni et al., 2019] who give an O_ε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.

Cite as

Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi},
  title =	{{Decremental Matching in General Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11},
  URN =		{urn:nbn:de:0030-drops-163528},
  doi =		{10.4230/LIPIcs.ICALP.2022.11},
  annote =	{Keywords: Dynamic algorithms, matching, primal-dual algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Authors: Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
Designing efficient dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms and has witnessed many exciting recent developments in, e.g., dynamic matching (Wajc STOC'20) and decremental shortest paths (Chuzhoy and Khanna STOC'19). Compared to other graph primitives (e.g. spanning trees and matchings), designing such algorithms for graph spanners and (more broadly) graph sparsifiers poses a unique challenge since there is no fast deterministic algorithm known for static computation and the lack of a way to adjust the output slowly (known as "small recourse/replacements"). This paper presents the first non-trivial efficient adaptive algorithms for maintaining many sparsifiers against an adaptive adversary. Specifically, we present algorithms that maintain 1) a polylog(n)-spanner of size Õ(n) in polylog(n) amortized update time, 2) an O(k)-approximate cut sparsifier of size Õ(n) in Õ(n^{1/k}) amortized update time, and 3) a polylog(n)-approximate spectral sparsifier in polylog(n) amortized update time. Our bounds are the first non-trivial ones even when only the recourse is concerned. Our results hold even against a stronger adversary, who can access the random bits previously used by the algorithms and the amortized update time of all algorithms can be made worst-case by paying sub-polynomial factors. Our spanner result resolves an open question by Ahmed et al. (2019) and our results and techniques imply additional improvements over existing results, including (i) answering open questions about decremental single-source shortest paths by Chuzhoy and Khanna (STOC'19) and Gutenberg and Wulff-Nilsen (SODA'20), implying a nearly-quadratic time algorithm for approximating minimum-cost unit-capacity flow and (ii) de-amortizing a result of Abraham et al. (FOCS'16) for dynamic spectral sparsifiers. Our results are based on two novel techniques. The first technique is a generic black-box reduction that allows us to assume that the graph is initially an expander with almost uniform-degree and, more importantly, stays as an almost uniform-degree expander while undergoing only edge deletions. The second technique is called proactive resampling: here we constantly re-sample parts of the input graph so that, independent of an adversary’s computational power, a desired structure of the underlying graph can be always maintained. Despite its simplicity, the analysis of this sampling scheme is far from trivial, because the adversary can potentially create dependencies between the random choices used by the algorithm. We believe these two techniques could be useful for developing other adaptive algorithms.

Cite as

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.ICALP.2022.20,
  author =	{Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He},
  title =	{{Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.20},
  URN =		{urn:nbn:de:0030-drops-163611},
  doi =		{10.4230/LIPIcs.ICALP.2022.20},
  annote =	{Keywords: dynamic graph algorithm, adaptive adversary, spanner, sparsifier}
}
Document
Track A: Algorithms, Complexity and Games
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Authors: Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [Sherman, 2017], optimal transport [Arun Jambulapati et al., 2019], and bipartite matching [Sepehr Assadi et al., 2022]. We develop efficient near-linear time, high-accuracy solvers for regularized variants of these games. Beyond the immediate applications of such solvers for computing Sinkhorn distances, a prominent tool in machine learning, we show that these solvers can be used to obtain improved running times for maintaining a (fractional) ε-approximate maximum matching in a dynamic decremental bipartite graph against an adaptive adversary. We give a generic framework which reduces this dynamic matching problem to solving regularized graph-structured optimization problems to high accuracy. Through our reduction framework, our regularized box-simplex game solver implies a new algorithm for dynamic decremental bipartite matching in total time Õ(m ⋅ ε^{-3}), from an initial graph with m edges and n nodes. We further show how to use recent advances in flow optimization [Chen et al., 2022] to improve our runtime to m^{1 + o(1)} ⋅ ε^{-2}, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of Õ(m ⋅ ε^{-4}) [Aaron Bernstein et al., 2020] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms.

Cite as

Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 77:1-77:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{jambulapati_et_al:LIPIcs.ICALP.2022.77,
  author =	{Jambulapati, Arun and Jin, Yujia and Sidford, Aaron and Tian, Kevin},
  title =	{{Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{77:1--77:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.77},
  URN =		{urn:nbn:de:0030-drops-164181},
  doi =		{10.4230/LIPIcs.ICALP.2022.77},
  annote =	{Keywords: bipartite matching, decremental matching, dynamic algorithms, continuous optimization, box-simplex games, primal-dual method}
}
Document
Beating the Folklore Algorithm for Dynamic Matching

Authors: Mohammad Roghani, Amin Saberi, and David Wajc

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence 2-approximate) matching in O(n) worst-case update time in n-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of both approximation ratio and worst-case update time. Specifically, we give a (2-Ω(1))-approximate algorithm with O(m^{3/8}) = O(n^{3/4}) worst-case update time in n-node, m-edge graphs. For sufficiently small constant ε > 0, no deterministic (2+ε)-approximate algorithm with worst-case update time O(n^{0.99}) was known. Our second result is the first deterministic (2+ε)-approximate weighted matching algorithm with O_ε(1)⋅ O(∜{m}) = O_ε(1)⋅ O(√n) worst-case update time. Neither of our results were previously known to be achievable by a randomized algorithm against an adaptive adversary. Our main technical contributions are threefold: first, we characterize the tight cases for kernels, which are the well-studied matching sparsifiers underlying much of the (2+ε)-approximate dynamic matching literature. This characterization, together with multiple ideas - old and new - underlies our result for breaking the approximation barrier of 2. Our second technical contribution is the first example of a dynamic matching algorithm whose running time is improved due to improving the recourse of other dynamic matching algorithms. Finally, we show how to use dynamic bipartite matching algorithms as black-box subroutines for dynamic matching in general graphs without incurring the natural 3/2 factor in the approximation ratio which such approaches naturally incur (reminiscent of the integrality gap of the fractional matching polytope in general graphs).

Cite as

Mohammad Roghani, Amin Saberi, and David Wajc. Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 111:1-111:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{roghani_et_al:LIPIcs.ITCS.2022.111,
  author =	{Roghani, Mohammad and Saberi, Amin and Wajc, David},
  title =	{{Beating the Folklore Algorithm for Dynamic Matching}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{111:1--111:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.111},
  URN =		{urn:nbn:de:0030-drops-157077},
  doi =		{10.4230/LIPIcs.ITCS.2022.111},
  annote =	{Keywords: dynamic matching, dynamic graph algorithms, sublinear algorithms}
}
Document
Incremental SCC Maintenance in Sparse Graphs

Authors: Aaron Bernstein, Aditi Dudeja, and Seth Pettie

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
In the incremental cycle detection problem, edges are added to a directed graph (initially empty), and the algorithm has to report the presence of the first cycle, once it is formed. A closely related problem is the incremental topological sort problem, where edges are added to an acyclic graph, and the algorithm is required to maintain a valid topological ordering. Since these problems arise naturally in many applications such as scheduling tasks, pointer analysis, and circuit evaluation, they have been studied extensively in the last three decades. Motivated by the fact that in many of these applications, the presence of a cycle is not fatal, we study a generalization of these problems, incremental maintenance of strongly connected components (incremental SCC). Several incremental algorithms in the literature which do cycle detection and topological sort in directed acyclic graphs, such as those by [Michael A. Bender et al., 2016] and [Haeupler et al., 2012], also generalize to maintain strongly connected components and their topological sort in general directed graphs. The algorithms of [Haeupler et al., 2012] and [Michael A. Bender et al., 2016] have a total update time of O(m^{3/2}) and O(m⋅ min{m^{1/2},n^{2/3}}) respectively, and this is the state of the art for incremental SCC. But the most recent algorithms for incremental cycle detection and topological sort ([Bernstein and Chechik, 2018] and [Bhattacharya and Kulkarni, 2020]), which yield total (randomized) update time Õ(min{m^{4/3}, n²}), do not extend to incremental SCC. Thus, there is a gap between the best known algorithms for these two closely related problems. In this paper, we bridge this gap by extending the framework of [Bhattacharya and Kulkarni, 2020] to general directed graphs. More concretely, we give a Las Vegas algorithm for incremental SCCs with an expected total update time of Õ(m^{4/3}). A key ingredient in the algorithm of [Bhattacharya and Kulkarni, 2020] is a structural theorem (first introduced in [Bernstein and Chechik, 2018]) that bounds the number of "equivalent" vertices. Unfortunately, this theorem only applies to DAGs. We show a natural way to extend this structural theorem to general directed graphs, and along the way we develop a significantly simpler and more intuitive proof of this theorem.

Cite as

Aaron Bernstein, Aditi Dudeja, and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.ESA.2021.14,
  author =	{Bernstein, Aaron and Dudeja, Aditi and Pettie, Seth},
  title =	{{Incremental SCC Maintenance in Sparse Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.14},
  URN =		{urn:nbn:de:0030-drops-145950},
  doi =		{10.4230/LIPIcs.ESA.2021.14},
  annote =	{Keywords: Directed Graphs, Strongly Connected Components, Dynamic Graph Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Beating Two-Thirds For Random-Order Streaming Matching

Authors: Sepehr Assadi and Soheil Behnezhad

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G = (V, E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use O(n ⋅ polylog) space, and output a large matching of G. We prove that for an absolute constant ε₀ > 0, one can find a (2/3 + ε₀)-approximate maximum matching of G using O(n log n) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3 + Ω(1))-approximation is achievable.

Cite as

Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2021.19,
  author =	{Assadi, Sepehr and Behnezhad, Soheil},
  title =	{{Beating Two-Thirds For Random-Order Streaming Matching}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.19},
  URN =		{urn:nbn:de:0030-drops-140887},
  doi =		{10.4230/LIPIcs.ICALP.2021.19},
  annote =	{Keywords: Maximum Matching, Streaming, Random-Order Streaming}
}
Document
Online Matching with Recourse: Random Edge Arrivals

Authors: Aaron Bernstein and Aditi Dudeja

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)


Abstract
The matching problem in the online setting models the following situation: we are given a set of servers in advance, the clients arrive one at a time, and each client has edges to some of the servers. Each client must be matched to some incident server upon arrival (or left unmatched) and the algorithm is not allowed to reverse its decisions. Due to this no-reversal restriction, we are not able to guarantee an exact maximum matching in this model, only an approximate one. Therefore, it is natural to study a different setting, where the top priority is to match as many clients as possible, and changes to the matching are possible but expensive. Formally, the goal is to always maintain a maximum matching while minimizing the number of changes made to the matching (denoted the recourse). This model is called the online model with recourse, and has been studied extensively over the past few years. For the specific problem of matching, the focus has been on vertex-arrival model, where clients arrive one at a time with all their edges. A recent result of Bernstein et al. [Bernstein et al., 2019] gives an upper bound of O (nlog² n) recourse for the case of general bipartite graphs. For trees the best known bound is O(nlog n) recourse, due to Bosek et al. [Bosek et al., 2018]. These are nearly tight, as a lower bound of Ω(nlog n) is known. In this paper, we consider the more general model where all the vertices are known in advance, but the edges of the graph are revealed one at a time. Even for the simple case where the graph is a path, there is a lower bound of Ω(n²). Therefore, we instead consider the natural relaxation where the graph is worst-case, but the edges are revealed in a random order. This relaxation is motivated by the fact that in many related models, such as the streaming setting or the standard online setting without recourse, faster algorithms have been obtained for the matching problem when the input comes in a random order. Our results are as follows: - Our main result is that for the case of general (non-bipartite) graphs, the problem with random edge arrivals is almost as hard as in the adversarial setting: we show a family of graphs for which the expected recourse is Ω(n²/log n). - We show that for some special cases of graphs, random arrival is significantly easier. For the case of trees, we get an upper bound of O(nlog²n) on the expected recourse. For the case of paths, this upper bound is O(nlog n). We also show that the latter bound is tight, i.e. that the expected recourse is at least Ω(nlog n).

Cite as

Aaron Bernstein and Aditi Dudeja. Online Matching with Recourse: Random Edge Arrivals. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.FSTTCS.2020.11,
  author =	{Bernstein, Aaron and Dudeja, Aditi},
  title =	{{Online Matching with Recourse: Random Edge Arrivals}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.11},
  URN =		{urn:nbn:de:0030-drops-132521},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.11},
  annote =	{Keywords: matchings, edge-arrival, online model}
}
Document
Online Carpooling Using Expander Decompositions

Authors: Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)


Abstract
We consider the online carpooling problem: given n vertices, a sequence of edges arrive over time. When an edge e_t = (u_t, v_t) arrives at time step t, the algorithm must orient the edge either as v_t → u_t or u_t → v_t, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog(n,T) maximum discrepancy (w.h.p) over any sequence of T arrivals, when the arriving edges are sampled independently and uniformly from any given graph G. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were O(√{n log n})-discrepancy for any adversarial sequence of arrivals, or O(log log n)-discrepancy bounds for the stochastic arrivals when G is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when G is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.

Cite as

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. Online Carpooling Using Expander Decompositions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2020.23,
  author =	{Gupta, Anupam and Krishnaswamy, Ravishankar and Kumar, Amit and Singla, Sahil},
  title =	{{Online Carpooling Using Expander Decompositions}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.23},
  URN =		{urn:nbn:de:0030-drops-132647},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.23},
  annote =	{Keywords: Online Algorithms, Discrepancy Minimization, Carpooling}
}
Document
Improved Bounds for Distributed Load Balancing

Authors: Sepehr Assadi, Aaron Bernstein, and Zachary Langley

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


Abstract
In the load balancing problem, the input is an n-vertex bipartite graph G = (C ∪ S, E) - where the two sides of the bipartite graph are referred to as the clients and the servers - and a positive weight for each client c ∈ C. The algorithm must assign each client c ∈ C to an adjacent server s ∈ S. The load of a server is then the weighted sum of all the clients assigned to it. The goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the 𝓁_∞-norm) or the 𝓁_p-norm of the server loads. This problem has a variety of applications and has been widely studied under several different names, including: scheduling with restricted assignment, semi-matching, and distributed backup placement. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity O(Δ⁵), where Δ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an O(log n / log log n)-approximation for unweighted clients and O(log²n/log log n)-approximation for weighted clients with round-complexity polylog(n). In this paper, we show the first distributed algorithms to compute an O(1)-approximation to the load balancing problem in polylog(n) rounds: - In the CONGEST model, we give an O(1)-approximation algorithm in polylog(n) rounds for unweighted clients. For weighted clients, the approximation ratio is O(log{n}). - In the less constrained LOCAL model, we give an O(1)-approximation algorithm for weighted clients in polylog(n) rounds. Our approach also has implications for the standard sequential setting in which we obtain the first O(1)-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all 𝓁_p-norms, including the 𝓁_∞-norm.

Cite as

Sepehr Assadi, Aaron Bernstein, and Zachary Langley. Improved Bounds for Distributed Load Balancing. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.DISC.2020.1,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary},
  title =	{{Improved Bounds for Distributed Load Balancing}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{1:1--1:15},
  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.1},
  URN =		{urn:nbn:de:0030-drops-130798},
  doi =		{10.4230/LIPIcs.DISC.2020.1},
  annote =	{Keywords: Load Balancing, Distributed Algorithms, Matching, Semi-Matching}
}
Document
Track A: Algorithms, Complexity and Games
Improved Bounds for Matching in Random-Order Streams

Authors: Aaron Bernstein

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph G = (V,E) are given as a stream e₁, …, e_m, and the algorithm is allowed to make a single pass over this stream while using O(n polylog(n)) space (m = |E| and n = |V|). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a 1/2-approximation in O(n) space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the 1/2-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a 2/3(∼.66)-approximate matching, but the space requirement is O(n^1.5 polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(n polylog(n)), but a worse approximation ratio of 6/11(∼.545), or 3/5(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 2/3(∼.66)-approximate matching using only O(n log(n)) space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a 1-1/e(∼.63)-approximation requires (n^{1+Ω(1/log log(n))}) space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams.

Cite as

Aaron Bernstein. Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bernstein:LIPIcs.ICALP.2020.12,
  author =	{Bernstein, Aaron},
  title =	{{Improved Bounds for Matching in Random-Order Streams}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.12},
  URN =		{urn:nbn:de:0030-drops-124194},
  doi =		{10.4230/LIPIcs.ICALP.2020.12},
  annote =	{Keywords: Graph Algorithms, Sublinear Algorithms, Matching, Streaming}
}
  • Refine by Author
  • 14 Bernstein, Aaron
  • 5 Assadi, Sepehr
  • 3 Dudeja, Aditi
  • 2 Disser, Yann
  • 2 Kopelowitz, Tsvi
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Dynamic graph algorithms
  • 4 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Online algorithms
  • 1 Computing methodologies → Description logics
  • Show More...

  • Refine by Keyword
  • 2 Load Balancing
  • 2 Matching
  • 2 Semi-Matching
  • 2 Streaming
  • 2 dynamic algorithms
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 5 2022
  • 4 2020
  • 3 2017
  • 2 2018
  • 2 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail