-
作者：Truong, Van-Anh
作者单位：Columbia University
摘要：We consider the single-item, multiperiod stochastic inventory problem with nonstationary and correlated demands. We provide the first proof that a well-known myopic policy, which we call look-ahead optimization (LA), is in fact an approximation algorithm for solving the large dynamic program that arises from this problem. We prove that LA provides the tightest known approximation bound for this problem. The expected cost of LA is at most twice the expected holding cost plus the expected backor...
-
作者：Blanchet, Jose; Lam, Henry
作者单位：Columbia University; Columbia University; Boston University
摘要：We develop rare-event simulation methodology for the analysis of loss events in a many-server loss system under the quality-driven regime, focusing on the steady-state loss probability (i.e., fraction of lost customers over arrivals) and the behavior of the whole system leading to loss events. The analysis of these events requires working with the full measure-valued process describing the system. This is the first algorithm that is shown to be asymptotically optimal, in the rare-event simulat...
-
作者：Tao, Zhijie; Zhou, Sean X.
作者单位：Shanghai University of Finance & Economics; Chinese University of Hong Kong
摘要：We consider a single-product, periodic-review inventory system with remanufacturable returned products, in which the serviceable product used to fulfill stochastic customer demand can be either manufactured from new parts or remanufactured from returned products. Demand and returns follow general stochastic processes and may be correlated, nonstationary, and evolving across different periods. The system costs include remanufacturing and manufacturing costs as well as inventory holding and dema...
-
作者：Gupta, Anupam; Nagarajan, Viswanath
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA
摘要：A covering integer program (CIP) is a mathematical program of the form min {c(T)x vertical bar Ax >= 1, 0 <= x <= u, x is an element of Z(n)}, where all entries in A, c, u are nonnegative. In the online setting, the constraints (i.e., the rows of the constraint matrix A) arrive over time, and the algorithm can only increase the coordinates of x to maintain feasibility. As an intermediate step, we consider solving the covering linear program (CLP) online, where the integrality constraints are d...
-
作者：Russo, Daniel; Van Roy, Benjamin
作者单位：Stanford University; Stanford University
摘要：This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multiarmed bandit problems. The algorithm, also known as Thompson Sampling and as probability matching, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical ...
-
作者：Hou, Ke; So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong; Chinese University of Hong Kong
摘要：In this paper, we establish hardness and approximation results for various L-p-ball constrained homogeneous polynomial optimization problems, where p is an element of [2,infinity]. Specifically, we prove that for any given d >= 3 and p is an element of [2,infinity], both the problem of optimizing a degree-d homogeneous polynomial over the L-p-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over L-p-balls are NP-hard. On the other hand, we show ...
-
作者：Megow, Nicole; Vredeveld, Tjark
作者单位：Technical University of Berlin; Maastricht University
摘要：We consider dynamic stochastic scheduling of preemptive jobs with processing times that follow independent discrete probability distributions. We derive a policy with a guaranteed performance ratio of 2 for the problem of minimizing the sum of weighted completion times on identical parallel machines subject to release dates. The analysis is tight. Our policy as well as their analysis applies also to the more general model of stochastic online scheduling. In contrast to previous results for non...
-
作者：Kratz, Peter
作者单位：Aix-Marseille Universite
摘要：We study a constrained stochastic control problem with jumps; the jump times of the controlled process are given by a Poisson process. The cost functional comprises quadratic components for an absolutely continuous control and the controlled process and an absolute value component for the control of the jump size of the process. We characterize the value function by a polynomial of degree two whose coefficients depend on the state of the system; these coefficients are given by a coupled system...
-
作者：Boros, Endre; Scozzari, Andrea; Tardella, Fabio; Veneziani, Pierangela
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; Niccolo Cusano Online University; Sapienza University Rome; State University of New York (SUNY) System; State University of New York (SUNY) Brockport
摘要：We consider the problem of finding upper and lower bounds for the probability of the union of events when the probabilities of the single events and the probabilities of the intersections of up to m events are given. It is known that the best possible bounds can be obtained by solving linear programming problems with a number of variables that is exponential in the number of events. Because of their size and structure, these large linear programs are known to be very hard to solve. In the lite...
-
作者：Ehlers, Lars; Klaus, Bettina
作者单位：Universite de Montreal; Universite de Montreal; University of Lausanne
摘要：In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA) mechanism with responsive strict priorities performs well, and economists have successfully implemented DA-mechanisms or slight va...
