2023 [ nach oben ]

Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill The st-Planar Edge Completion Problem Is Fixed-Parameter TractableInternational Symposium Algorithms and Computation (ISAAC) 2023: 46:1–46:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The problem of deciding whether a biconnected planar digraph \(G = (V, E)\) can be augmented to become an st-planar graph by adding a set of oriented edges \(E′ \subseteq V \times V\) is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set \(E′\).
@inproceedings{DBLP:conf/isaac/KhazaliyaKLMS23, abstract = {The problem of deciding whether a biconnected planar digraph \(G = (V, E)\) can be augmented to become an st-planar graph by adding a set of oriented edges \(E′ \subseteq V \times V\) is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set \(E′\).}, author = {Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill}, booktitle = {International Symposium Algorithms and Computation (ISAAC)}, keywords = {isaac kirillsimonov year2023}, pages = {46:1–46:13}, title = {The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable}, year = 2023 }

2021 [ nach oben ]

Antoniadis, Antonios; Kumar, Gunjan; Kumar, Nikhil Skeletons and Minimum Energy SchedulingInternational Symposium on Algorithms and Computation (ISAAC) 2021: 51:1–51:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Consider the problem where \(n\) jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires \(q\) energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.
@inproceedings{antoniadis2021skeletons, abstract = {Consider the problem where \(n\) jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires \(q\) energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.}, author = {Antoniadis, Antonios and Kumar, Gunjan and Kumar, Nikhil}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {isaac nikhilkumar year2021}, pages = {51:1-51:16}, title = {Skeletons and Minimum Energy Scheduling}, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip-Schelling-Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge u,vis monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge u,v makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o (1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
@inproceedings{blasius2021impact, abstract = {Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip-Schelling-Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v}is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o (1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise}, booktitle = {International Symposium on Algorithms and Computation, (ISAAC) 2021}, keywords = {sys:relevantfor:ae isaac louisemolitor martinskrejca thomasblaesius tobiasfriedrich year2021}, pages = {29:1–29:17}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}, volume = 212, year = 2021 }

2020 [ nach oben ]

Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on FacesInternational Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.
@inproceedings{kumar2020multicommodity, abstract = {We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.}, author = {Kumar, Nikhil}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {isaac nikhilkumar year2020}, pages = {1-11}, title = {Multicommodity Flows in Planar Graphs with Demands on Faces}, year = 2020 }

2016 [ nach oben ]

Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning Building Clusters with Lower-Bounded SizesInternational Symposium on Algorithms and Computation (ISAAC) 2016: 4:1–4:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios however the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality \(k\) without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomial-time solvable cases for \(k = 2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).
@inproceedings{DBLP:conf/isaac/Abu-KhzamBCF16, abstract = {Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios however the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality \(k\) without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomial-time solvable cases for \(k = 2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).}, author = {Abu{-}Khzam, Faisal N. and Bazgan, Cristina and Casel, Katrin and Fernau, Henning}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, editor = {Hong, Seok{-}Hee}, keywords = {cristinabazgan faisalnabukhzam hen isaac katrincasel year2016}, pages = {4:1-4:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Building Clusters with Lower-Bounded Sizes}, volume = 64, year = 2016 }

2015 [ nach oben ]

Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik Many-to-one Matchings with Lower Quotas: Algorithms and ComplexityInternational Symposium Algorithms and Computation (ISAAC) 2015: 176–187
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \($u_max$\) as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).
@inproceedings{arulselvan2015manytoone, abstract = {We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $u_max$ as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).}, author = {Arulselvan, Ashwin and Cseh, Ágnes and Groß, Martin and Manlove, David F. and Matuschke, Jannik}, booktitle = {International Symposium Algorithms and Computation (ISAAC)}, keywords = {sys:relevantfor:ae agnescseh ashwinarulselvan davidfmanlove isaac jannikmatuschke martingroß year2015}, pages = {176-187}, title = {Many-to-one Matchings with Lower Quotas: Algorithms and Complexity}, year = 2015 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchInternational Symposium of Algorithms and Computation (ISAAC) 2015: 140–150
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.
@inproceedings{DBLP:conf/isaac/FriedrichKKS15, abstract = {Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.}, address = {Berlin, Heidelberg}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {International Symposium of Algorithms and Computation (ISAAC)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, keywords = {andrewmsutton isaac martinskrejca timokoetzing tobiasfriedrich year2015}, pages = {140-150}, publisher = {Springer Berlin Heidelberg}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2015 }

Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Unbounded Discrepancy of Deterministic Random Walks on GridsInternational Symposium on Algorithms and Computation (ISAAC) 2015: 212–222
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on \(\mathbb{Z}^d\) the single vertex discrepancy is only a constant \(c_d\). Other authors also determined the precise value of \(c_d\) for \(d=1,2\). All these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph \(\mathbb{Z}^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions \(d \ge 1\) and arbitrary discrepancies \(\ell \ge 0\), we construct configurations that reach a discrepancy of at least \(\ell\).
@inproceedings{DBLP:conf/isaac/FriedrichKK15, abstract = {Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on \(\mathbb{Z}^d\) the single vertex discrepancy is only a constant \(c_d\). Other authors also determined the precise value of \(c_d\) for \(d=1,2\). All these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph \(\mathbb{Z}^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions \(d \ge 1\) and arbitrary discrepancies \(\ell \ge 0\), we construct configurations that reach a discrepancy of at least \(\ell\).}, author = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {antonkrohmer imported isaac maximiliankatzmann tobiasfriedrich year2015}, pages = {212-222}, series = {Lecture Notes in Computer Science}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 9472, year = 2015 }

2012 [ nach oben ]

Friedrich, Tobias; Krohmer, Anton Parameterized Clique on Scale-Free NetworksInternational Symposium on Algorithms and Computation (ISAAC) 2012: 659–668
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with \(n\) nodes and power law exponent \(\gamma\), cliques of size \(k\) can be found in time \(O(n^2)\) for \(\gamma \ge 3\) and in time \(O(n, exp(k^4))\) for \(2<\gamma <3\).
@inproceedings{DBLP:conf/isaac/FriedrichK12, abstract = {Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with \(n\) nodes and power law exponent \(\gamma\), cliques of size \(k\) can be found in time \(O(n^2)\) for \(\gamma \ge 3\) and in time \(O(n\, exp(k^4))\) for \(2<\gamma <3\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {antonkrohmer imported isaac tobiasfriedrich year2012}, pages = {659-668}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Parameterized Clique on Scale-Free Networks}, volume = 7676, year = 2012 }

2011 [ nach oben ]

Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary DimensionsInternational Symposium on Algorithms and Computation (ISAAC) 2011: 190–199
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also 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 w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^1/d/r+\log n)\) rounds.
@inproceedings{DBLP:conf/isaac/FriedrichSS11, abstract = {A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also 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 w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^{1/d}/r+\log n)\) rounds.}, author = {Friedrich, Tobias and Sauerwald, Thomas and Stauffer, Alexandre}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported isaac tobiasfriedrich year2011}, pages = {190-199}, series = {Lecture Notes in Computer Science}, title = {Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions}, volume = 7074, year = 2011 }

2008 [ nach oben ]

Friedrich, Tobias; Hebbinghaus, Nils Average Update Times for Fully-Dynamic All-Pairs Shortest PathsInternational Symposium of Algorithms and Computation (ISAAC) 2008: 692–703
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the fully-dynamic all pairs shortest path problem for graphs with arbitrary non-negative edge weights. It is known for digraphs that an update of the distance matrix costs \(O(n^{2.75})\) worst-case time Thorup, STOC '05 and \(O(n^2)\) amortized time Demetrescu and Italiano, J.ACM '04 where \(n\) is the number of vertices. We present the first average-case analysis of the undirected problem. For a random update we show that the expected time per update is bounded by \(O(n^{4/3 + \epsilon)\) for all \(\epsilon > 0\).
@inproceedings{DBLP:conf/isaac/FriedrichH08, abstract = {We study the fully-dynamic all pairs shortest path problem for graphs with arbitrary non-negative edge weights. It is known for digraphs that an update of the distance matrix costs \(O(n^{2.75})\) worst-case time Thorup, STOC '05 and \(O(n^2)\) amortized time Demetrescu and Italiano, J.ACM '04 where \(n\) is the number of vertices. We present the first average-case analysis of the undirected problem. For a random update we show that the expected time per update is bounded by \(O(n^{4/3} + \epsilon)\) for all \(\epsilon > 0\).}, author = {Friedrich, Tobias and Hebbinghaus, Nils}, booktitle = {International Symposium of Algorithms and Computation (ISAAC)}, keywords = {isaac noabstract tobiasfriedrich year2008}, pages = {692-703}, title = {Average Update Times for Fully-Dynamic All-Pairs Shortest Paths}, year = 2008 }

Bringmann, Karl; Friedrich, Tobias Approximating the Volume of Unions and Intersections of High-Dimensional Geometric ObjectsInternational Symposium on Algorithms and Computation (ISAAC) 2008: 436–447
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time \(2^{d^{1-\epsilon}}\)-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time \(\epsilon\)-approximation.
@inproceedings{DBLP:conf/isaac/BringmannF08, abstract = {We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is \#P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are \#P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove \#P-hardness for boxes and show that there is no multiplicative polynomial-time \(2^{d^{1-\epsilon}}\)-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time \(\epsilon\)-approximation.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported isaac tobiasfriedrich year2008}, pages = {436-447}, series = {Lecture Notes in Computer Science}, title = {Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects}, volume = 5369, year = 2008 }

2007 [ nach oben ]

Ajwani, Deepak; Friedrich, Tobias Average-Case Analysis of Online Topological OrderingInternational Symposium on Algorithms and Computation (ISAAC) 2007: 464–475
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of \(O(n^2 \text{polylog(n))\) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound \(O(n^{2.75})\) for this problem.
@inproceedings{DBLP:conf/isaac/AjwaniF07, abstract = {Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of \(O(n^2 \text{polylog}(n))\) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound \(O(n^{2.75})\) for this problem.}, author = {Ajwani, Deepak and Friedrich, Tobias}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported isaac tobiasfriedrich year2007}, pages = {464-475}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Average-Case Analysis of Online Topological Ordering}, volume = 4835, year = 2007 }

2006 [ nach oben ]

Doerr, Benjamin; Friedrich, Tobias Deterministic Random Walks on the Two-Dimensional GridInternational Symposium on Algorithms and Computation (ISAAC) 2006: 474–483
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.
@inproceedings{DBLP:conf/isaac/DoerrF06, abstract = {Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.}, author = {Doerr, Benjamin and Friedrich, Tobias}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported isaac tobiasfriedrich year2006}, pages = {474-483}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Deterministic Random Walks on the Two-Dimensional Grid}, volume = 4288, year = 2006 }