We address the problem of modeling energy resource allocation, including dispatch, storage, and the long-term investments in new technologies, capturing different sources of uncertainty such as energy from wind, deman...
详细信息
We address the problem of modeling energy resource allocation, including dispatch, storage, and the long-term investments in new technologies, capturing different sources of uncertainty such as energy from wind, demands, prices, and rainfall. We also wish to model long-term investment decisions in the presence of uncertainty. Accurately modeling the value of all investments, such as wind turbines and solar panels, requires handling fine-grained temporal variability and uncertainty in wind and solar in the presence of storage. We propose a modeling and algorithmic strategy based on the framework of approximate dynamic programming (ADP) that can model these problems at hourly time increments over an entire year or several decades. We demonstrate the methodology using both spatially aggregate and disaggregate representations of energy supply and demand. This paper describes the initial proof of concept experiments for an ADP-based model called SMART;we describe the modeling and algorithmic strategy and provide comparisons against a deterministic benchmark as well as initial experiments on stochastic data sets.
Given a set S of N distinct elements in random order and a pivot x is an element of S, we study the problem of simultaneously finding the left and the right neighbors of x, i.e., L = max{u/u x). We analyze an adaptiv...
详细信息
Given a set S of N distinct elements in random order and a pivot x is an element of S, we study the problem of simultaneously finding the left and the right neighbors of x, i.e., L = max{u/u < x} and R = min(v/v > x). We analyze an adaptive algorithm that solves this problem by scanning the set S while maintaining current values for the neighbors L and R. Each new element inspected is compared first against the neighbor in the most populous side, then (if necessary) against the neighbor in the other side, and finally (if necessary), against the pivot. This algorithm may require 3N comparisons in the worst case, but it performs well on the average. If the pivot has rank alphaN, where alpha is fixed and < 1/2, the algorithm does (1 + )N + Theta (log N) comparisons on the average, with a variance of 3 ln N + Theta (1). However, in the case where the pivot is the median, the average becomes 3/2 N + Theta (rootN), while the variance grows to (1/2 - pi /8)N + Theta (log N). We also prove that, in the alphaN case, the limit distribution is Gaussian.
Options are popular and important financial instruments in world financial markets. One of the simplest options is European call option, which is a contract giving its holder the right, but not the obligation, to buy ...
详细信息
Options are popular and important financial instruments in world financial markets. One of the simplest options is European call option, which is a contract giving its holder the right, but not the obligation, to buy a stock or other financial asset at some point in the future (called the expiration date) for a specified price X (called the strike price). The payoff of an option is the amount of money its holder makes on the contract. Suppose that we have a European option on a stock, and the stock price S is more than the strike price X on the expiration date. Then, we can make some money by exercising the option to buy the stock and selling the stock immediately at the market price. Hence, the payoff of a European option is given by (S — X)~+ = max{S — X, 0}. The price of the option is usually much less than the actual price of the underlying stock. Therefore, options hedge risk more cheaply than stocks only, and provide a chance to get large profit with a small amount of money if one's speculation is good.
In this paper we perform an amortized analysis of a functional program for splaying. We construct a potential function that yields the same bound for the amortized cost of splaying as given by D.D. Sleator and R.E. Ta...
详细信息
In this paper we perform an amortized analysis of a functional program for splaying. We construct a potential function that yields the same bound for the amortized cost of splaying as given by D.D. Sleator and R.E. Tarjan - the inventors of splay trees. In addition, we show that this bound is minimal for the class of ''sum of logs'' potentials. Our approach also applies to the analysis of path reversal and pairing heaps.
We provide here a complete average-case analysis of the binary continued fraction representation of a random rational whose numerator and denominator are odd and less than N, We analyze the three main parameters of th...
详细信息
We provide here a complete average-case analysis of the binary continued fraction representation of a random rational whose numerator and denominator are odd and less than N, We analyze the three main parameters of the binary continued fraction expansion, namely, the height, the number of steps of the binary Euclidean algorithm, and finally the sum of the exponents of powers of 2 contained in the numerators of the binary continued fraction. The average values of these parameters are shown to be asymptotic to A(i) log N, and the three constants A(i) are related to the invariant measure of the Perron-Frobenius operator linked to this dynamical system. The binary Euclidean algorithm was previously studied in 1976 by Brent who provided a partial analysis of the number of steps, based on a heuristic model and some unproven conjecture. Our methods are quite different, not relying on unproven assumptions, and more general, since they allow us to study all the parameters of the binary continued fraction expansion.
In this era of giga-scale integration, thermal analysis has become one of the hot topics in VLSI chip design. Active thermal sources may be abstracted as a set of weighted points on a 2D chip-floor. The conventional n...
详细信息
In this era of giga-scale integration, thermal analysis has become one of the hot topics in VLSI chip design. Active thermal sources may be abstracted as a set of weighted points on a 2D chip-floor. The conventional notion of discrepancy that deals with the congestion properties of a set of scattered points may not be able to capture properly all real-life instances in this context. In this paper, we have introduced a new concept, called the density of a region to study some of the properties of the distribution of these weighted points. We prove several counter-intuitive results concerning the properties of the regions that have maximum or minimum density. We then outline algorithms for recognizing these regions. We also compare the attributes of density with the existing concept of discrepancy. (C) 2008 Elsevier B.V. All rights reserved.
A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive...
详细信息
A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive rate is a key to understanding the Bloom filter and applications that use it. We show experimentally that the classic analysis for false positive rate is wrong. We formally derive a correct formula using a balls-and-bins model and show how to numerically compute the new, correct formula in a stable manner. We also prove that the new formula always results in a predicted greater false positive rate than the classic formula. This correct formula is numerically compared to the classic formula for relative error - for a small Bloom filter the prediction of false positive rate will be in error when the classic formula is used. (C) 2010 Elsevier B.V. All rights reserved.
In this paper, a formal convergence analysis of the conventional PSO algorithms with time-varying parameters is presented. Based on this analysis, a new convergence-related parametric model for the conventional PSO is...
详细信息
In this paper, a formal convergence analysis of the conventional PSO algorithms with time-varying parameters is presented. Based on this analysis, a new convergence-related parametric model for the conventional PSO is introduced. Finally, several new schemes for parameter adjustment, providing significant performance benefits, are introduced. Performance of these schemes is empirically compared to conventional PSO algorithms on a set of selected benchmarks. The tests prove effectiveness of the newly introduced schemes, especially regarding their ability to efficiently explore the search space. (C) 2009 Elsevier B.V. All rights reserved.
J.M. Kurtzberg proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km × km assignment problem is decomposed into k 2...
详细信息
J.M. Kurtzberg proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km × km assignment problem is decomposed into k 2 problems of size m × m and one problem of size k × k . In this paper we analyze the performance of this heuristic, obtaining the following main results: 1. (1) For the maximization problem, the ratio of the optimal solution to the heuristic solution can be as large as, but cannot exceed min( k , m ); 2. (2) For the minimization problem, if k = o( n /log n ) where n = mk , and the matrix elements are independently drawn from a uniform distribution on (0, 1), in the limit the expected value of the heuristic solution is at least k /3 times that of the optimal solution.
We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadline...
详细信息
We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a 3/2-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论