124 research outputs found
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free
No full textA t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior.
In particular, our main result is that, for (2k-1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n^{4/3}) edges that is robust to f = O(n^{2/9}) edge faults. It is well known that Ω(n^{4/3}) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k
Senator Henry M. Jackson sitting at a table during a private dinner meeting with Israeli Ambassador Simcha Dinitz and Prime Minister Menachem Begin, Washington, D.C., June 17, 1977
No full textHandwritten on verso: L to right - Ambassador Dinitz, Senator Jackson, P.M. Begin. 6/17/77
Caption filed with photograph: Meeting with Begin, June 17, 1977. Left to right - Ambassador Dinitz, Senator Jackson, Prime Minister Begin
The existence of square integer Heffter arrays
No full text An integer Heffter array H(m, n; s, t) is an m × n partially filled matrix with entries from the set {±1, ±2, . . ., ±ms} such that i) each row contains s filled cells and each column contains t filled cells, ii) every row and column sums to 0 (in Z), and iii) no two entries agree in absolute value. Heffter arrays are useful for embedding the complete graph K 2 ms +1 on an orientable surface in such a way that each edge lies between a face bounded by an s-cycle and a face bounded by a t-cycle. In 2015, Archdeacon, Dinitz, Donovan and Yazıcı constructed square (i.e. m = n) integer Heffter arrays for many congruence classes. In this paper we construct square integer Heffter arrays for all the cases not found in that paper, completely solving the existence problem for square integer Heffter arrays. </p
Square integer Heffter arrays with empty cells
No full textA Heffter array H(m,n;s,t) is an m×n matrix with nonzero entries from (Formula presented.) such that (i) each row contains s filled cells and each column contains t filled cells, (ii) every row and column sum to 0, and (iii) no element from {x,-x} appears twice. Heffter arrays are useful in embedding the complete graph (Formula presented.) on an orientable surface where the embedding has the property that each edge borders exactly one s-cycle and one t-cycle. Archdeacon, Boothby and Dinitz proved that these arrays can be constructed in the case when s=m, i.e every cell is filled. In this paper we concentrate on square arrays with empty cells where every row sum and every column sum is 0 in Z. We solve most of the instances of this case
The Capacity of Smartphone Peer-To-Peer Networks
No full textWe study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartphone operating systems. The capacity of a network expresses how much sustained throughput can be maintained for a set of communication demands, and is therefore a fundamental bound on the usefulness of a network. Because of this importance, wireless network capacity has been active area of research for the last two decades.
The three capacity problems that we study differ in the structure of the communication demands. The first problem is pairwise capacity, where the demands are (source, destination) pairs. Pairwise capacity is one of the most classical definitions, as it was analyzed in the seminal paper of Gupta and Kumar on wireless network capacity. The second problem we study is broadcast capacity, in which a single source must deliver packets to all other nodes in the network. Finally, we turn our attention to all-to-all capacity, in which all nodes must deliver packets to all other nodes. In all three of these problems we characterize the optimal achievable throughput for any given network, and design algorithms which asymptotically match this performance. We also study these problems in networks generated randomly by a process introduced by Gupta and Kumar, and fully characterize their achievable throughput.
Interestingly, the techniques that we develop for all-to-all capacity also allow us to design a one-shot gossip algorithm that runs within a polylogarithmic factor of optimal in every graph. This largely resolves an open question from previous work on the one-shot gossip problem in this model
Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies
No full textEmerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities
23: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 29.01.2018
No full text23 |
0:00:00 Starten
0:07:03 Flüsse und Ford Fulkerson
0:08:39 Max Flow - Min Cut
0:12:42 Dinitz: Distanz Label
0:14:37 Dinitz: Schichtgraph
0:15:45 Dinitz: Blockierender Fluss
0:17:21 Dinitz: Blockierender Fluss Operationen
0:20:36 Dinitz: Kosten pro Blockierender Fluss
0:24:14 Dinitz: Laufzeit
0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network
0:30:24 Maximum Cardinality Bipartite Matching
0:31:35 Preflow-Push Algorithms
0:34:00 Level Function
0:36:49 Procedure genericPreflowPush
1:21:53 Searching for Eligible Edges
1:23:50 Satz 11. Arbitrary Preflow Push finds a maximum flow in time O (n²m
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract)
No full textYe m Dinitz Shlomo Moran Sergio Rajsbaum Abstract We consider a failure-free, asynchronous message passing network, with n processors arranged on a ring or a chain. The processes are identically programmed but have distinct identities, taken from f1; : : : ; Mg. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF ( nding the maximum identity, a restricted version of Leader). We show that in both chain and ring topologies, somewhat surprisingly, the message complexities of all three tasks are the same. Hence, we suggest as a ner measure of complexity the number of bits transmitted, BitC(). We show that in chains, w.r.t. this measure, Consensus is easier than Leader, which is easier than MaxF. More speci cally, we prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC(Consensus) = 2 and BitC(Leader) = BitC(MaxF) = 2 log 2 M O(1). For a chain, BitC(Consensus) = (n), and BitC(MaxF) = (n log M ). When the length is even BitC(Leader) = (n), while if the length is odd BitC(Leader) = (n + log M )
A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
No full textThe problem of finding a minimum weight k-vertex connected spanning subgraph in a graph G = (V; E) is considered. For k 2, this problem is known to be NP-hard. Combining properties of inclusionminimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there exist k internally vertex-disjoint paths to every other vertex), we derive an auxiliary polynomial time algorithm for finding a (d k 2 e+1)-connected subgraph with a weight at most twice the optimum to the original problem. In particular, we obtain a 2-approximation algorithm for the case k = 3 of our problem. This improves the best previously known approximation ratio 3. The complexity of the algorithm is O(jV j 3 jEj) = O(jV j 5 ). Up to 1990, E. A. Dinic, Moscow. y Dept. of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel. E-mail: [email protected]. z This work was done as a part of the author's D.Sc. thesis at the ..
On the approximation of the single source k-splittable flow problem
No full textAbstractThis work deals with the minimum congestion single-source k-splittable flow problem: given a network and a set of terminal pairs sharing a common source node, the aim is to route concurrently all demands using at most k supporting paths for each commodity and minimizing the congestion on arcs. Dinitz et al. proposed in [Y. Dinitz, N. Garg, M.X. Goemans, On the single-source unsplittable flow problem, Combinatorica 19 (1999) 17–41] the best known constant factor approximated algorithm for the case of k=1, namely the single source unsplittable case. Here we consider an adaptation of such an algorithm to the k-splittable case. Moreover, we propose a heuristic improvement of the first step of this algorithm, that provides experimentally better results without affecting the approximation guarantee of the algorithm
- …
