An official website of the United States government
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in \Otil(n^{5/3 }m^{1/3}) time\footnote{The \Otil(\cdot) notation hides \poly(\log n) factors}. The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon the best previously known running time of \tilde{O}(\min\{n^{\omega},m\sqrt{n},m^{4/3}\}) for m >> n^{7/4} (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute \eps-approximate effective resistances for a set SS of vertex pairs via approximate Schur complements in \Otil(m+(n + |S|)\eps^{-2}) time, without using the Johnson-Lindenstrauss lemma which requires \Otil( \min\{(m + |S|)\eps^{-2}, m+n\eps^{-4} +|S|\eps^{-2}\}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.
more »
« less
Experimental Evaluation of Energy Transfers by an Energy Packet Switch in a Digital Microgrid
In this paper, we experimentally demonstrate the performance of the recently proposed Energy Packet Switch (EPS) for energy distribution. The N × M EPS aggregates the energy from N sources and dispatches energy to M outputs, each of which feeds one or many loads. Energy is distributed from a source to a load in the form of energy packets. The operation of the EPS is an enabler device to realize a digital microgrid. We carry out exhaustive experiments to show that the EPS grants energy to keep demand satisfied and even in cases when the demand overwhelms the EPS capacity. Results of the experiments show that the EPS ably grants all energy requests that fall within its capacity, and it controls the distribution of energy under extenuating conditions by approaching a level of fairness. The experiments also show the average time that a request waits for the corresponding grant.
more »
« less
- Award ID(s):
- 1641033
- PAR ID:
- 10124363
- Date Published:
- Journal Name:
- 019 IEEE 7th International Conference on Smart Energy Grid Engineering (SEGE)
- Page Range / eLocation ID:
- 1-6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of efficiently estimating the effect of an intervention on a single variable using observational samples. Our goal is to give algorithms with polynomial time and sample complexity in a non-parametric setting. Tian and Pearl (AAAI ’02) have exactly characterized the class of causal graphs for which causal effects of atomic interventions can be identified from observational data. We make their result quantitative. Suppose 𝒫 is a causal model on a set V of n observable variables with respect to a given causal graph G, and let do(x) be an identifiable intervention on a variable X. We show that assuming that G has bounded in-degree and bounded c-components (k) and that the observational distribution satisfies a strong positivity condition: (i) [Evaluation] There is an algorithm that outputs with probability 2/3 an evaluator for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The evaluator can return in O(n) time the probability P^(v) for any assignment v to V. (ii) [Sampling] There is an algorithm that outputs with probability 2/3 a sampler for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The sampler returns an iid sample from P^ with probability 1 in O(n) time. We extend our techniques to estimate P(Y | do(x)) for a subset Y of variables of interest. We also show lower bounds for the sample complexity, demonstrating that our sample complexity has optimal dependence on the parameters n and eps, as well as if k=1 on the strong positivity parameter.more » « less
-
We present a feasibility analysis of the controlled delivery power grid (CDG) that uses aggregated power request by users to reduce communications overhead. The CDG, as an approach to the power grid, uses a data network to communicate requests and grants of power in the distribution of electrical power. These requests and grants allow the energy supplier know the power demand in advance and to designate the loads and the time when power is supplied to them. Each load is assigned a power-network address that is used for communication of requests and grants with the energy supplier. With addressed loads, power is only delivered to selected loads. However, issuing a request for power before delivery takes place requires knowing the demand of power the load consumes during the operation interval. However, it is a general concern that having issuing requests in a time-slot basis may risk request losses and therefore, generate intermittent supply. Therefore, we propose request aggregation to minimize the number of requests issued. We show by simulation that the CDG with request aggregation attains high performance, in terms of satisfaction ratio and waiting time for power supply.more » « less
-
This work seeks to quantify the benefits of using energy storage toward the reduction of the energy generation cost of a power system. A two-fold optimization framework is provided where the first optimization problem seeks to find the optimal storage schedule that minimizes operational costs. Since the operational cost depends on the storage capacity, a second optimization problem is then formulated with the aim of finding the optimal storage capacity to be deployed. Although, in general, these problems are difficult to solve, we provide a lower bound on the cost savings for a parametrized family of demand profiles. The optimization framework is numerically illustrated using real-world demand data from ISO New England. Numerical results show that energy storage can reduce energy generation costs by at least 2.5 percent.more » « less
-
On-demand warehousing platforms match companies with underutilized warehouse and distribution capabilities with customers who need extra space or distribution services. These new business models have unique advantages, in terms of reduced capacity and commitment granularity, but also have different cost structures compared with traditional ways of obtaining distribution capabilities. This research is the first quantitative analysis to consider distribution network strategies given the advent of on-demand warehousing. Our multi-period facility location model – a mixed-integer linear program – simultaneously determines location-allocation decisions of three distribution center types (self-distribution, 3PL/lease, on-demand). A simulation model operationally evaluates the impact of the planned distribution strategy when various uncertainties can occur. Computational experiments for a company receiving products produced internationally to fulfil a set of regional customer demands illustrate that the power of on-demand warehousing is in creating hybrid network designs that more efficiently use self-distribution facilities through improved capacity utilization. However, the business case for on-demand warehousing is shown to be influenced by several factors, namely on-demand capacity availability, responsiveness requirements, and demand patterns. This work supports a firm’s use of on-demand warehousing if it has tight response requirements, for example for same-day delivery; however, if a firm has relaxed response requirements, then on-demand warehousing is only recommended if capacity availability of planned on-demand services is high. We also analyze capacity flexibility options leased by third-party logistics companies for a premium price and draw attention to the importance of them offering more granular solutions to stay competitive in the market.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/SEGE.2019.8859844
