Browsing by Subject "Dynamic programming"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Automated application robustification based on outlier detection
    (2013-08) Suresh, Amoghavarsha
    In this thesis, we propose automated algorithmic error resilience based on outlier detection. Our approach employs metric functions that normally produce metric values according to a designed distribution or behavior and produce outlier values (i.e., values that do not conform to the designed distribution or behavior) when computations are affected by errors. Thus, for our robust algorithms, error detection becomes equivalent to outlier detection. Our error resilient algorithms use outlier detection not only to detect errors, but also to aid in reducing the amount of redundancy required to produce correct results when errors are detected. Our error-resilient algorithms incur significantly lower overhead than traditional hardware and software error resilience techniques. Also, compared to previous approaches to application-based error resilience, our approaches parameterize the robustification process, making it easy to automatically transform large classes of applications into robust applications with the use of parser-based tools and minimal programmer effort. We demonstrate the use of automated error resilience based on outlier detection for two important classes of applications, namely, structured grid and dynamic programming problems, leveraging the flexibility of algorithmic error resilience to achieve improved application robustness and lower overhead compared to previous error resilience approaches.
  • Thumbnail Image
    Item
    Dynamic resource allocation in wireless fading channels with delay requirements.
    (2010-01) Lee, Juyul
    In this dissertation we investigate resource allocation in fading channels with delay constraints. We first consider scheduling communication resources over time-varying channels when constrained by a hard deadline requirement. The basic problem setting is given as follows: a packet of B bits must be transmitted by a hard deadline of T time slots over a time-varying channel. The transmitter/scheduler must determine how many bits to transmit, or equivalently how much energy to transmit with, during each time slot based on the current channel quality and the number of unserved bits, with the objective of minimizing expected total energy. Our focus is on the interplay between opportunism (adapting to the fading behavior) and the delay requirements. Under the Shannon energy cost function, the optimal solution can only be numerically determined in general, and thus we develop simple and near-optimal policies, which are shown to be asymptotically optimal. Then, we consider monomial cost, under which we can obtain the optimal policy in closed form. We attempt to extend the result to the case for multi-user scheduling and scheduling with outage. In these resource allocation problems, our interests are in formulating an analytical solution. Additionally, we consider parallel/MIMO channel scheduling and wideband scheduling with a hard deadline constraint. As an alternative view of delay requirements, we consider the fairness of each user's traffic. In this regard, we investigate the symmetric capacity of MIMO broadcast channels along with high SNR analysis of MIMO broadcast channels.
  • Thumbnail Image
    Item
    Essays on Stochastic Inventory Systems
    (2015-07) Chen, Rui
    This thesis consists of three essays in stochastic inventory systems. The first essay is on the impact of input price variability and correlation on stochastic inventory systems. For a general class of such systems, we show that the expected cost function is concave in the input price. From this, it follows that higher input price variability in the sense of the convex order always leads to lower expected cost. We show that this is true under a wide range of assumptions for price evolution, including cases with i.i.d. prices and cases where prices are correlated and evolve according to an AR(1) process, a geometric Brownian motion, or a Markovian martingale. In addition, the result holds in cases where there is just a single period. We also examine the impact of price correlation over time and across inputs, and we find that expected cost is increasing in price correlation over time and decreasing in price correlation across components. We present results of a numerical study that provide insights on how various parameters influence the effects of price variability and correlation. The second essay is on the optimal control of inventory systems with stochastic and independent leadtimes. We show that a fixed base-stock policy is sub-optimal and can perform poorly. For the case of exponentially distributed leadtimes, we show that the optimal policy is state-dependent and specified in terms of an inventory-dependent threshold function. Moreover, we show that this threshold function is non-increasing in the inventory level and characterized by at most m parameters. That is, once the threshold function starts to decrease it continues to decrease with a rate that is at least one. Taking advantage of this structure, we develop an efficient algorithm for computing these parameters. In characterizing the structure of the optimal policy, we rely on an application of the Banach fixed point theorem. We compare the performance of the optimal policy to that of simpler heuristics. We also extend our analysis to systems with lost sales and systems with order cancellations. The third essay is on the optimal policies for inventory systems with concave ordering costs. By extending the Scarf (1959} model to systems with piecewise linear concave ordering costs, we characterize the structure of optimal policies for periodic review inventory systems with concave ordering costs and general demand distributions. We show that, except for a bounded region, the generalized (s,S) policy is optimal. We do so by (a) introducing a conditional monotonicity property for the optimal order-up-to levels and (b) applying the notion of c-convexity. We also provide conditions under which the generalized (s, S) policy is optimal for all regions of the state space.