2024 [ nach oben ]

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Tree Containment Above Minimum Degree is FPTSymposium on Discrete Algorithms (SODA) 2024: 366–376
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Abstract According to the classic Chvatal's Lemma from 1977, a graph of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvatal's Lemma: For any \(n\)-vertex graph G, integer \(k\), and a tree \(T\) on at most \(\delta(G)+k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\), can be done in time \(f(k) · n^\mathcal{O(1)}\) for some function \(f\) of \(k\) only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. The full version of the paper can be accessed at https://arxiv.org/abs/2310.09678.
@inproceedings{fomin2024containment, abstract = {Abstract According to the classic Chvatal's Lemma from 1977, a graph of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvatal's Lemma: For any \(n\)-vertex graph G, integer \(k\), and a tree \(T\) on at most \(\delta(G)+k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\), can be done in time \(f(k) · n^{\mathcal{O}(1)}\) for some function \(f\) of \(k\) only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. The full version of the paper can be accessed at https://arxiv.org/abs/2310.09678.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {kirillsimonov soda year2024}, pages = {366-376}, title = {Tree Containment Above Minimum Degree is FPT}, year = 2024 }

2023 [ nach oben ]

Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Tuukka; Simonov, Kirill; Stamoulis Giannοs Fixed-Parameter Tractability of Maximum Colored Path and BeyondSymposium on Discrete Algorithms (SODA) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \($n$\)-vertex undirected graph, vertices \($s$\) and \($t$\), and an integer \($k$\), finds an \($(s,t)$\)-path containing at least \($k$\) different colors in time \($2^k n^\mathcal{O(1)}$\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman~[SODA~2012] on finding a path through \($k$\) specified vertices. It also implies the first \($2^k n^\mathcal{O(1)}$\) time algorithm for finding an \($(s,t)$\)-path of length at least \($k$\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \($n$\)-vertex undirected graph \($G$\), a matroid \($M$\) whose elements correspond to the vertices of \($G$\) and which is represented over a finite field of order \($q$\), a positive integer weight function on the vertices of \($G$\), two sets of vertices \($S,T subseteq V(G)$\), and integers \($p,k,w$\), and the task is to find \($p$\) vertex-disjoint paths from \($S$\) to \($T$\) so that the union of the vertices of these paths contains an independent set of \($M$\) of cardinality \($k$\) and weight \($w$\), while minimizing the sum of the lengths of the paths. We give a \($2^p+\mathcal{O(k^2 log (q+k)) n^\mathcal{O w$\) time randomized algorithm for this problem.
@inproceedings{fomin2023fixedparameter, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored $n$-vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$-path containing at least $k$ different colors in time $2^k n^{\mathcal{O}(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{\mathcal{O}(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$-vertex undirected graph $G$, a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$, two sets of vertices $S,T \subseteq V(G)$, and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$, while minimizing the sum of the lengths of the paths. We give a $2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}} w$ time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Simonov, Kirill and Stamoulis, Giannοs}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2023}, title = {Fixed-Parameter Tractability of Maximum Colored Path and Beyond}, year = 2023 }

2022 [ nach oben ]

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Algorithmic Extensions of Dirac’s TheoremSymposium on Discrete Algorithms (SODA) 2022: 406–416
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^\mathcal{O(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^\mathcal{O(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O(k^2 log (q+k)) n^\mathcal{O(1) w\) time randomized algorithm for this problem.
@inproceedings{fomin2022algorithmic, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj{ö}rklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^{\mathcal{O}(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T \subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w\) time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2022}, pages = {406-416}, title = {Algorithmic Extensions of Dirac's Theorem}, year = 2022 }

2021 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, Ralf The Impact of Heterogeneity and Geometry on the Proof Complexity of Random SatisfiabilitySymposium on Discrete Algorithms (SODA) 2021: 42–53
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
@inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {andreasgoebel jordilevy ralfrothenberger soda thomasblaesius tobiasfriedrich year2021}, pages = {42-53}, publisher = {SIAM}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

2020 [ nach oben ]

Antoniadis, Antonios; Garg, Naveen; Kumar‎, Gunjan; Kumar, Nikhil Parallel Machine Scheduling to Minimize Energy ConsumptionSymposium on Discrete Algorithms (SODA) 2020: 2758–2769
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given \(n\) jobs with release dates, deadlines and processing times we consider the problem of scheduling them on \(m\) parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.
@inproceedings{antoniadis2020parallel, abstract = {Given \(n\) jobs with release dates, deadlines and processing times we consider the problem of scheduling them on \(m\) parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.}, author = {Antoniadis, Antonios and Garg, Naveen and Kumar‎, Gunjan and Kumar, Nikhil}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {antoniosantoniadis gunjankumar naveengarg nikhilkumar soda year2020}, pages = {2758-2769}, title = {Parallel Machine Scheduling to Minimize Energy Consumption}, year = 2020 }

2019 [ nach oben ]

Chechik, Shiri; Cohen, Sarel Near Optimal Algorithms For The Single Source Replacement Paths ProblemSymposium on Discrete Algorithms (SODA) 2019: 2090–2109
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.
@inproceedings{chechik2019optimal, abstract = {The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O}}(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.}, author = {Chechik, Shiri and Cohen, Sarel}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae sarelcohen shirichechik soda year2019}, pages = {2090-2109}, title = {Near Optimal Algorithms For The Single Source Replacement Paths Problem}, year = 2019 }

2017 [ nach oben ]

Chechik, Shiri; Cohen, Sarel; Fiat, Amos; Kaplan, Haim \( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance OraclesSymposium on Discrete Algorithms (SODA) 2017: 1479–1496
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O(\frac{\log n\log \log n ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^2+ \mathcal{O(1) \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.
@inproceedings{chechik2017varepsilonapproximate, abstract = {An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O}(\frac{\log n}{\log \log n} ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O}(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^{2+ \mathcal{O}(1)} \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.}, author = {Chechik, Shiri and Cohen, Sarel and Fiat, Amos and Kaplan, Haim}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae amosfiat haimkaplan sarelcohen shirichechik soda year2017}, pages = {1479-1496}, title = {\( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance Oracles}, year = 2017 }

2013 [ nach oben ]

Bläsius, Thomas; Rutter, Ignaz Simultaneous PQ-Ordering with Applications to Constrained Embedding ProblemsSymposium on Discrete Algorithms (SODA) 2013: 1030–1043
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.
@inproceedings{DBLP:conf/soda/BlasiusR13, abstract = {In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {soda thomasblaesius year2013}, pages = {1030-1043}, title = {Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems}, year = 2013 }

2011 [ nach oben ]

Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas Randomized Diffusion for Indivisible LoadsSymposium on Discrete Algorithms (SODA) 2011: 429–439
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.
@inproceedings{DBLP:conf/soda/BerenbrinkCFFS11, abstract = {We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.}, author = {Berenbrink, Petra and Cooper, Colin and Friedetzky, Tom and Friedrich, Tobias and Sauerwald, Thomas}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {imported soda tobiasfriedrich year2011}, pages = {429-439}, title = {Randomized Diffusion for Indivisible Loads}, year = 2011 }

2010 [ nach oben ]

Bradonjic, Milan; Elsässer, Robert; Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Efficient Broadcast on Random Geometric GraphsSymposium on Discrete Algorithms (SODA) 2010: 1412–1421
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
A Random Geometric Graph (RGG) in two dimensions is constructed by distributing \(n\) nodes independently and uniformly at random in \([0, \sqrt n]^2\) and creating edges between every pair of nodes having Euclidean distance at most \(r\), for some prescribed \(r\). We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability \(1 - O(n^{-1})\) this algorithm informs every node in the largest connected component of an RGG within \(O(\sqrt n / r + \log n)\) rounds. This holds for any value of \(r\) larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in \([0, \sqrt n]^2\), the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is \(\Theta(\sqrt n / r\)), which surprisingly has been an open problem so far.
@inproceedings{DBLP:conf/soda/BradonjicEFSS10, abstract = {A Random Geometric Graph (RGG) in two dimensions is constructed by distributing \(n\) nodes independently and uniformly at random in \([0, \sqrt n]^2\) and creating edges between every pair of nodes having Euclidean distance at most \(r\), for some prescribed \(r\). We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability \(1 - O(n^{-1})\) this algorithm informs every node in the largest connected component of an RGG within \(O(\sqrt n / r + \log n)\) rounds. This holds for any value of \(r\) larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in \([0, \sqrt n]^2\), the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is \(\Theta(\sqrt n / r\)), which surprisingly has been an open problem so far.}, author = {Bradonjic, Milan and Elsässer, Robert and Friedrich, Tobias and Sauerwald, Thomas and Stauffer, Alexandre}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {imported soda tobiasfriedrich year2010}, pages = {1412-1421}, title = {Efficient Broadcast on Random Geometric Graphs}, year = 2010 }

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load BalancingSymposium on Discrete Algorithms (SODA) 2010: 1620–1629
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On \(d\)-dimensional torus graphs with \(n\) nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121-130] can deviate up to \(\Omega(\text{polylog(n))\), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694-705] has a deviation of \(\Omega(n^{1/d})\). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.
@inproceedings{DBLP:conf/soda/FriedrichGS10, abstract = {We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On \(d\)-dimensional torus graphs with \(n\) nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121-130] can deviate up to \(\Omega(\text{polylog}(n))\), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694-705] has a deviation of \(\Omega(n^{1/d})\). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.}, author = {Friedrich, Tobias and Gairing, Martin and Sauerwald, Thomas}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {imported soda tobiasfriedrich year2010}, pages = {1620-1629}, title = {Quasirandom Load Balancing}, year = 2010 }

2008 [ nach oben ]

Cooper, Joshua N.; Doerr, Benjamin; Friedrich, Tobias; Spencer, Joel Deterministic random walks on regular treesSymposium on Discrete Algorithms (SODA) 2008: 766–772
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Jim Propp’s rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid \(\mathbb{Z}^d\) and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite \(k\)-ary tree (\(k \geq 3\)), we show that for any deviation \(D\) there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least \(D\) more chips than expected in the random walk model. However, to achieve a deviation of \(D\) it is necessary that at least \(k^{\Theta(D)}\) vertices contribute by being occupied by a number of chips not divisible by \(k\) in a certain time interval.
@inproceedings{DBLP:conf/soda/CooperDFS08, abstract = {Jim Propp’s rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid \(\mathbb{Z}^d\) and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite \(k\)-ary tree (\(k \geq 3\)), we show that for any deviation \(D\) there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least \(D\) more chips than expected in the random walk model. However, to achieve a deviation of \(D\) it is necessary that at least \(k^{\Theta(D)}\) vertices contribute by being occupied by a number of chips not divisible by \(k\) in a certain time interval.}, author = {Cooper, Joshua N. and Doerr, Benjamin and Friedrich, Tobias and Spencer, Joel}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {noabstract soda tobiasfriedrich year2008}, pages = {766-772}, title = {Deterministic random walks on regular trees}, year = 2008 }