Goran Zuzic

Last Name

Zuzic

First Name

Goran

ORCID

0000-0002-9322-6329

Show all metadata

Search Results

Publications 1 - 10 of 15

Low-Congestion shortcuts without embedding
Haeupler, Bernhard; Izumi, Taisuke; Zuzic, Goran (2021)
Distributed Computing
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. This phenomenon can be seen as the broad underlying reason for the pervasive Ω~(√n+D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, [Ghaffari and Hauepler; SODA’16] introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA’16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem—even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining tree-restricted shortcuts: a more structured and restricted form of shortcuts. We give a novel construction algorithm which efficiently finds such shortcuts that are, up to a logarithmic factor, as good as the best restricted shortcuts that exist for a given network. This new construction algorithm directly leads to an O(DlogO(1)n)-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist—without the need to compute any embedding. This greatly simplifies the existing planar algorithms and includes the first efficient algorithm for bounded genus graphs.
Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
Anagnostides, Ioannis; Lenzen, Christoph; Haeupler, Bernhard; et al. (2023)
Distributed Computing
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after n°⁽¹⁾SQ(G)log(1/ϵ) rounds, where ϵ>0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω˜(SQ(G)) rounds, even for a crude solution with ϵ≤1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D⋅n°⁽¹⁾log(1/ϵ) rounds, where D is the hop-diameter of the network; as well as n°⁽¹⁾log(1/ϵ)-round algorithms for the case of SQ(G)≤n°⁽¹⁾, which holds for most networks of interest. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique model. In this model, we show the existence of a Laplacian solver with round complexity n°⁽¹⁾log(1/ϵ). The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel ρ-congested generalization of the standard part-wise aggregation problem, which could be of independent interest.
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
Zuzic, Goran; Haeupler, Bernhard; Roeyskoe, Antti (2023)
PODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
The packet routing problem asks to select routing paths that minimize the maximum edge congestion for a set of packets specified by source-destination vertex pairs. We revisit a semi-oblivious approach to this problem: each source-destination pair is assigned a small set of well-chosen predefined paths before the demand is revealed, while the sending rates along the paths can be optimally adapted to the demand. This approach has been considered in practice in network traffic engineering due to its superior robustness and performance as compared to both oblivious routing and traditional traffic engineering approaches.We show the existence of sparse semi-oblivious routings: only O(log n) paths are selected between each pair of vertices. The routing is (poly log n)-competitive for all demands against the offline-optimal congestion objective, even on worst-case graphs. Even for the well-studied case of hypercubes, no such result was known: our deterministic and oblivious selection of O(log n) paths is the first simple construction of a deterministic oblivious structure that nearoptimally assigns source-destination pairs to few routes. Prior work shows that a deterministic selection of a single path in a hypercube yields unacceptable performance; our results contrast the current solely-negative landscape of results for semi-oblivious routing. We give the sparsity-competitiveness trade-off for lower sparsities and nearly match it with a lower bound.Our construction is extremely simple: Sample the few paths from any competitive oblivious routing. Indeed, this natural construction was used in traffic engineering as an unproven heuristic. We give a satisfactory theoretical justification for their empirical effectiveness: the competitiveness of the construction improves exponentially with the number of paths. In other words, semi-oblivious routing benefits from the power of random choices. Finally, when combined with the recent hop-constrained oblivious routing, we also obtain sparse and competitive structures for the completion-time objective.
Hop-constrained oblivious routing
Ghaffari, Mohsen; Haeupler, Bernhard; Zuzic, Goran (2021)
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion + dilation), defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion + dilation) within a poly(logn) factor of the best possible value. More precisely, for any integer hop-bound h, this oblivious routing scheme selects paths of length at most h · poly(logn) and is poly(logn)-competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most h hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which are O(logn)-competitive in terms of congestion, but are not competitive in terms of dilation.
Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver
Anagnostides, Ioannis; Lenzen, Christoph; Haeupler, Bernhard; et al. (2022)
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
This paper refines the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if > 0 is the error of the Laplacian solver, we obtain two main results.
A Simple Boosting Framework for Transshipment
Zuzic, Goran (2023)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 31st Annual European Symposium on Algorithms (ESA 2023)
Transshipment is an important generalization of both the shortest path problem and the optimal transport problem. The task asks to route a demand using a flow of minimum cost over (uncapacitated) edges. Transshipment has recently received extensive attention in theoretical computer science as it is the centerpiece of all modern theoretical breakthroughs in parallel and distributed (approximate) shortest-path computation, a classic and well-studied problem. The key advantage of transshipment over shortest paths is the so-called boosting property: one can often boost a crude approximate solution to a (near-optimal) (1 + ε)-approximate solution. However, our understanding of this phenomenon is limited: it is not clear which approximators can be boosted. Moreover, all current boosting frameworks are built with a specific type of approximator in mind and are relatively complicated. The main takeaway of our paper is conceptual: any black-box oracle that computes an approximate dual solution can be boosted to an (1 + ε)-approximator. This decouples and simplifies all known near-optimal (1 + ε)-approximate transshipment and shortest paths results: they all (implicitly) construct approximate dual solutions and boost them. We provide a very simple analysis based on the multiplicative weights framework. Furthermore, to keep the paper completely self-contained, we provide a new (and arguably much simpler) analysis of multiplicative weights that leverages well-known optimization tools to bypass the ad-hoc calculations used in the standard analyses.
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Rozhoň, Václav; Haeupler, Bernhard; Martinsson, Anders; et al. (2023)
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only logO(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.
Network Coding Gaps for Completion Times of Multiple Unicasts
Haeupler, Bernhard; Wajc, David; Zuzic, Goran (2020)
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Anagnostides, Ioannis; Lenzen, Christoph; Haeupler, Bernhard; et al. (2022)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 36th International Symposium on Distributed Computing (DISC 2022)
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after no(1)SQ(G) log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires (Equation presented)(SQ(G)) rounds, even for a crude solution with ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D · no(1) log(1/ε) rounds, where D is the hop-diameter of the network; as well as no(1) log(1/ε)-round algorithms for the case of SQ(G) ≤ no(1), which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further independent applications in the future.
Undirected (1+𝜀)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms
Rozhoň, Václav; Grunau, Christoph; Haeupler, Bernhard; et al. (2022)
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
This paper presents near-optimal deterministic parallel and distributed algorithms for computing (1+eps)-approximate single-source shortest paths in any undirected weighted graph. On a high level, we deterministically reduce this and other shortest-path problems to Õ(1) Minor-Aggregations. A Minor-Aggregation computes an aggregate (e.g., max or sum) of node-values for every connected component of some subgraph. Our reduction immediately implies: Optimal deterministic parallel (PRAM) algorithms with Õ(1) depth and near-linear work. Universally-optimal deterministic distributed (CONGEST) algorithms, whenever deterministic Minor-Aggregate algorithms exist. For example, an optimal Õ(hopDiameterG)-round deterministic CONGEST algorithm for excluded-minor networks. Several novel tools developed for the above results are interesting in their own right: A local iterative approach for reducing shortest path computations "up to distance D"to computing low-diameter decompositions "up to distance D/2". Compared to the recursive vertex-reduction approach of [Li20], our approach is simpler, suitable for distributed algorithms, and eliminates many derandomization barriers. A simple graph-based Õ(1)-competitive g.,"1-oblivious routing based on low-diameter decompositions that can be evaluated in near-linear work. The previous such routing [ZGY+20] was no(1)-competitive and required no(1) more work. A deterministic algorithm to round any fractional single-source transshipment flow into an integral tree solution. The first distributed algorithms for computing Eulerian orientations.

Publications 1 - 10 of 15

Goran Zuzic

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results