The Experts below are selected from a list of 318 Experts worldwide ranked by ideXlab platform
David R. Karger - One of the best experts on this subject based on the ideXlab platform.
-
a randomized fully polynomial time approximation scheme for the all terminal network Reliability Problem
Siam Review, 2001Co-Authors: David R. KargerAbstract:The classic all-terminal network Reliability Problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This Problem has obvious applications in the design of communication networks. Since the Problem is ${\sharp {\cal P}}$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of $k$-connectivity, strong connectivity in directed Eulerian graphs and $r$-way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514].
-
a randomized fully polynomial time approximation scheme for the all terminal network Reliability Problem
SIAM Journal on Computing, 1999Co-Authors: David R. KargerAbstract:The classic all-terminal network Reliability Problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This Problem has obvious applications in the design of communication networks. Since the Problem is $\SP$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described.
-
A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
arXiv: Data Structures and Algorithms, 1998Co-Authors: David R. KargerAbstract:The classic all-terminal network Reliability Problem posits a graph, each of whose edges fails independently with some given probability.
-
a randomized fully polynomial time approximation scheme for the all terminal network Reliability Problem
Symposium on the Theory of Computing, 1995Co-Authors: David R. KargerAbstract:The classic all-terminal network Reliability Problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This Problem has obvious ap- plications in the design of communication networks. Since the Problem isP-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approxima- tion scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and 1/� an estimate for the failure probability that is accurate to within a relative error of 1 ± � with high probability. We also give a deterministic polyno- mial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication (D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492-514).
Tadashi Wadayama - One of the best experts on this subject based on the ideXlab platform.
-
probabilistic analysis of the network Reliability Problem on a random graph ensemble
International Symposium on Information Theory and its Applications, 2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdős-Renyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F 2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
ISITA - Probabilistic analysis of the network Reliability Problem on a random graph ensemble
2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdős-Renyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F 2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
Probabilistic analysis of the network Reliability Problem on a random graph ensemble
2012 International Symposium on Information Theory and its Applications, 2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdos-Rényi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
Probabilistic Analysis on Network Reliability Problem
arXiv: Information Theory, 2011Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:The network Reliability Problem for evaluating the network failure probability has been extensively studied. For a given undirected graph $G$, the network failure probability is the probability such that edge failures make $G$ unconnected. It is assumed that edge failures occur independently with the same probability. In this paper, a probabilistic analysis on the network Reliability Problem will be shown. We assume a simple random graph model closely related to the Erd\H{o}s-R\'{e}nyi random graph. By using the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$, we have derived upper and lower bounds on expected network failure probability. The ensemble analysis used here is very similar to the analysis on the input-output weight distribution of a low-density generator matrix code with column weight 2.
-
probabilistic analysis of the network Reliability Problem on a random graph ensemble
arXiv: Information Theory, 2011Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph $G$, the network failure probability is the probability that edge failures (i.e., edge erasures) make $G$ unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erd\H{o}s-R\'{e}nyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$. The present study shows a close relationship between the ensemble analysis of the network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.
Akiyuki Yano - One of the best experts on this subject based on the ideXlab platform.
-
probabilistic analysis of the network Reliability Problem on a random graph ensemble
International Symposium on Information Theory and its Applications, 2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdős-Renyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F 2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
ISITA - Probabilistic analysis of the network Reliability Problem on a random graph ensemble
2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdős-Renyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F 2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
Probabilistic analysis of the network Reliability Problem on a random graph ensemble
2012 International Symposium on Information Theory and its Applications, 2012Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erdos-Rényi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cutset space of G is a linear space over F2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the average weight distribution of LDGM codes with column weight 2.
-
Probabilistic Analysis on Network Reliability Problem
arXiv: Information Theory, 2011Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:The network Reliability Problem for evaluating the network failure probability has been extensively studied. For a given undirected graph $G$, the network failure probability is the probability such that edge failures make $G$ unconnected. It is assumed that edge failures occur independently with the same probability. In this paper, a probabilistic analysis on the network Reliability Problem will be shown. We assume a simple random graph model closely related to the Erd\H{o}s-R\'{e}nyi random graph. By using the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$, we have derived upper and lower bounds on expected network failure probability. The ensemble analysis used here is very similar to the analysis on the input-output weight distribution of a low-density generator matrix code with column weight 2.
-
probabilistic analysis of the network Reliability Problem on a random graph ensemble
arXiv: Information Theory, 2011Co-Authors: Akiyuki Yano, Tadashi WadayamaAbstract:In the field of computer science, the network Reliability Problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph $G$, the network failure probability is the probability that edge failures (i.e., edge erasures) make $G$ unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erd\H{o}s-R\'{e}nyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$. The present study shows a close relationship between the ensemble analysis of the network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.
Osman Yağan - One of the best experts on this subject based on the ideXlab platform.
-
CDC - On the network Reliability Problem of the heterogeneous key predistribution scheme
2016 IEEE 55th Conference on Decision and Control (CDC), 2016Co-Authors: Rashad Eletreby, Osman YağanAbstract:We consider the network Reliability Problem in wireless sensor networks secured by the heterogeneous random key predistribution scheme. This scheme generalizes Eschenauer-Gligor scheme by considering the cases when the network comprises sensor nodes with varying level of resources; e.g., regular nodes vs. cluster heads. The scheme induces the inhomogeneous random key graph, denoted G(n; μ, K, P). We analyze the Reliability of G(n; μ, K, P) against random link failures. Namely, we consider G(n; μ, K, P, α) formed by deleting each edge of G(n; μ, K, P) independently with probability 1−α, and study the probability that the resulting graph i) has no isolated node; and ii) is connected. We present scaling conditions onK, P, and α such that both events take place with probability zero or one, respectively, as the number of nodes gets large. We present numerical results to support these in the finite-node regime.
-
On the network Reliability Problem of the heterogeneous key predistribution scheme
2016 IEEE 55th Conference on Decision and Control (CDC), 2016Co-Authors: Rashad Eletreby, Osman YağanAbstract:We consider the network Reliability Problem in wireless sensor networks secured by the heterogeneous random key predistribution scheme. This scheme generalizes Eschenauer-Gligor scheme by considering the cases when the network comprises sensor nodes with varying level of resources; e.g., regular nodes vs. cluster heads. The scheme induces the inhomogeneous random key graph, denoted G(n; μ, K, P). We analyze the Reliability of G(n; μ, K, P) against random link failures. Namely, we consider G(n; μ, K, P, α) formed by deleting each edge of G(n; μ, K, P) independently with probability 1-α, and study the probability that the resulting graph i) has no isolated node; and ii) is connected. We present scaling conditions onK, P, and α such that both events take place with probability zero or one, respectively, as the number of nodes gets large. We present numerical results to support these in the finite-node regime.
Bethany A. Frew - One of the best experts on this subject based on the ideXlab platform.
-
low cost solution to the grid Reliability Problem with 100 penetration of intermittent wind water and solar for all purposes
Proceedings of the National Academy of Sciences of the United States of America, 2015Co-Authors: Mark Z Jacobson, Mary A Cameron, Mark A Delucchi, Bethany A. FrewAbstract:This study addresses the greatest concern facing the large-scale integration of wind, water, and solar (WWS) into a power grid: the high cost of avoiding load loss caused by WWS variability and uncertainty. It uses a new grid integration model and finds low-cost, no-load-loss, nonunique solutions to this Problem on electrification of all US energy sectors (electricity, transportation, heating/cooling, and industry) while accounting for wind and solar time series data from a 3D global weather model that simulates extreme events and competition among wind turbines for available kinetic energy. Solutions are obtained by prioritizing storage for heat (in soil and water); cold (in ice and water); and electricity (in phase-change materials, pumped hydro, hydropower, and hydrogen), and using demand response. No natural gas, biofuels, nuclear power, or stationary batteries are needed. The resulting 2050–2055 US electricity social cost for a full system is much less than for fossil fuels. These results hold for many conditions, suggesting that low-cost, reliable 100% WWS systems should work many places worldwide.
-
Low-cost solution to the grid Reliability Problem with 100% penetration of intermittent wind, water, and solar for all purposes
Proceedings of the National Academy of Sciences, 2015Co-Authors: Mark Z Jacobson, Mary A Cameron, Mark A Delucchi, Bethany A. FrewAbstract:This study addresses the greatest concern facing the large-scale integration of wind, water, and solar (WWS) into a power grid: the high cost of avoiding load loss caused by WWS variability and uncertainty. It uses a new grid integration model and finds low-cost, no-load-loss, nonunique solutions to this Problem on electrification of all US energy sectors (electricity, transportation, heating/cooling, and industry) while accounting for wind and solar time series data from a 3D global weather model that simulates extreme events and competition among wind turbines for available kinetic energy. Solutions are obtained by prioritizing storage for heat (in soil and water); cold (in ice and water); and electricity (in phase-change materials, pumped hydro, hydropower, and hydrogen), and using demand response. No natural gas, biofuels, nuclear power, or stationary batteries are needed. The resulting 2050–2055 US electricity social cost for a full system is much less than for fossil fuels. These results hold for many conditions, suggesting that low-cost, reliable 100% WWS systems should work many places worldwide.
