Zobrazeno 1 - 10
of 45
pro vyhledávání: '"Zuzic, Goran"'
This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that guarantee a polylog-competitive completion-ti
Externí odkaz:
http://arxiv.org/abs/2403.07410
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
Externí odkaz:
http://arxiv.org/abs/2301.06647
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One application is
Externí odkaz:
http://arxiv.org/abs/2210.16351
Autor:
Ghaffari, Mohsen, Zuzic, Goran
We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in $\widetilde{O}(D + \sqrt{n})$ rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nano
Externí odkaz:
http://arxiv.org/abs/2205.14967
This paper presents near-optimal deterministic parallel and distributed algorithms for computing $(1+\varepsilon)$-approximate single-source shortest paths in any undirected weighted graph. On a high level, we deterministically reduce this and other
Externí odkaz:
http://arxiv.org/abs/2204.05874
We provide universally-optimal distributed graph algorithms for $(1+\varepsilon)$-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any $n$-node network $
Externí odkaz:
http://arxiv.org/abs/2110.15944
Autor:
Zuzic, Goran
Transshipment, also known under the names of earth mover's distance, uncapacitated min-cost flow, or Wasserstein's metric, is an important and well-studied problem that asks to find a flow of minimum cost that routes a general demand vector. Adding t
Externí odkaz:
http://arxiv.org/abs/2110.11723
Autor:
Anagnostides, Ioannis, Lenzen, Christoph, Haeupler, Bernhard, Zuzic, Goran, Gouleakis, Themis
In this paper, we refine the (almost) \emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (almost) \emph{universally optimal} distributed Laplacian solver. Specif
Externí odkaz:
http://arxiv.org/abs/2109.05151
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster
Externí odkaz:
http://arxiv.org/abs/2104.03932
Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorithms which use these embeddings seem inherently randomized and ill-suite
Externí odkaz:
http://arxiv.org/abs/2102.05168