BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Sebastian Forster

Sebastian Forster contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2026arXiv

Fully Dynamic Spectral Sparsification for Directed Hypergraphs

There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of \textit{directed} hypergraphs. Our algorithm achieves a near-optimal size of $O(n^2 / \varepsilon ^2 \log ^7 m)$ and amortized update time of $O(r^2 \log ^3 m)$, where $n$ is the number of vertices, and $m$ and $r$ respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any $k$ hyperedge insertions or deletions can be processed with $O(kr^2 \log ^3 m)$ amortized work and $O(\log ^2 m)$ depth. This constitutes the first spectral-based sparsification algorithm in this setting.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Dynamic algorithms for k-center on graphs

In this paper we give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into $k$ sets by choosing $k$ centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than $2$ approximation for this problem. While in many applications the input may naturally be modeled as a graph, all prior works on $k$-center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental $(2+ε)$-approximation algorithm and a randomized incremental $(4+ε)$-approximation algorithm, both with amortized update time $kn^{o(1)}$ for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic $(2+ε)$-approximation algorithm for the $k$-center problem, with worst-case update time that is within a factor $k$ of the state-of-the-art fully dynamic $(1+ε)$-approximation single-source shortest paths algorithm in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a $(2+ε)$-approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast Deterministic Fully Dynamic Distance Approximation

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain improved dynamic algorithms that, given an unweighted and undirected graph $G=(V,E)$ undergoing edge insertions and deletions, and a parameter $ 0 < ε\leq 1 $, maintain $(1+ε)$-approximations of the $st$-distance between a given pair of nodes $ s $ and $ t $, the distances from a single source to all nodes (&#34;SSSP&#34;), the distances from multiple sources to all nodes (&#34;MSSP&#34;), or the distances between all nodes (&#34;APSP&#34;). Our main result is a deterministic algorithm for maintaining $(1+ε)$-approximate $st$-distance with worst-case update time $O(n^{1.407})$ (for the current best known bound on the matrix multiplication exponent $ω$). This even improves upon the fastest known randomized algorithm for this problem. Similar to several other well-studied dynamic problems whose state-of-the-art worst-case update time is $O(n^{1.407})$, this matches a conditional lower bound [BNS, FOCS 2019]. We further give a deterministic algorithm for maintaining $(1+ε)$-approximate single-source distances with worst-case update time $O(n^{1.529})$, which also matches a conditional lower bound. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining $(1+ε, β)$-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improved randomized algorithms for several problems such as exact $st$-distances and diameter approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Faster Cut Sparsification of Weighted Graphs

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pmε)$. This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/ε^2)$. Our algorithm computes such a sparsifier in time $O(m\cdot\min(α(n)\log(m/n),\log (n)))$, both for graphs with polynomially bounded and unbounded integer weights, where $α(\cdot)$ is the functional inverse of Ackermann&#39;s function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an $M$-partial MSF packing of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$, where $F_i$ is a maximum spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minor Sparsifiers and the Distributed Laplacian Paradigm

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetildeΩ(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP&#39;18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Laplacian Paradigm in the Broadcast Congested Clique

In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford (FOCS 2014). We show how to solve certain linear programs up to additive error $ε$ with $n$ constraints on an $n$-vertex Broadcast Congested Clique network in $\tilde O(\sqrt{n}\log(1/ε))$ rounds. Using this, we show how to find an exact solution to the minimum cost flow problem in $\tilde O(\sqrt{n})$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $1 + \varepsilon$ in undirected graphs with non-negative edge weights using a tailored gradient descent algorithm. Using $\tilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ (the number of nodes in the graph), our gradient descent algorithm takes $\tilde O(\varepsilon^{-2})$ iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of $\operatorname{polylog} n$. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior work by obtaining the following results: (1) Broadcast CONGEST model: $(1 + \varepsilon)$-approximate SSSP using $\tilde{O}((\sqrt{n} + D)\varepsilon^{-3})$ rounds, where $ D $ is the (hop) diameter of the network. (2) Broadcast congested clique model: $(1 + \varepsilon)$-approximate transshipment and SSSP using $\tilde{O}(\varepsilon^{-2})$ rounds. (3) Multipass streaming model: $(1 + \varepsilon)$-approximate transshipment and SSSP using $\tilde{O}(n)$ space and $\tilde{O}(\varepsilon^{-2})$ passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative edge weights that are polynomially bounded in $n$; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications

We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $ or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (for edge weights polynomial in $ n $). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA &#39;20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design. For dynamic distance oracles, our result is the first to break the $ O (\sqrt{m}) $ update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, further applications of our result in dynamic approximation algorithms are conceivable. From a technical perspective, we obtain our main result by first designing a decremental algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal&#39;s ball-growing approach [FOCS &#39;96] with the pruning framework of Chechik and Zhang [SODA &#39;20]. We then extend this to a fully dynamic algorithm by enriching a well-known &#39;decremental to fully dynamic&#39; reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction.

0 citations0 reviewsNo code linkedOpen access