-
作者：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 ...
-
作者：Wu, Jingchen; Chao, Xiuli
作者单位：University of Michigan System; University of Michigan; University of Michigan System; University of Michigan
摘要：In this paper we study a stochastic production/inventory system with finite production capacity and random demand. The cumulative production and demand are modeled by a two-dimensional Brownian motion process. There is a setup cost for switching on the production and a convex holding and shortage cost, and our objective is to find the optimal production/inventory control that minimizes the average cost. Both lost-sales and backlog cases are studied. For the lost-sales model we show that, withi...
-
作者：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 ...
-
作者：Chen, Ning; Gravin, Nick; Lu, Pinyan
作者单位：Nanyang Technological University; Microsoft; Microsoft Research Asia; Microsoft; Microsoft China
摘要：In the generalized assignment problem (gap), a set of jobs seek to be assigned to a set of machines. For every job-machine pair, there are a specific value and an accommodated capacity for the assignment. The objective is to find an assignment that maximizes the total sum of values given that the capacity constraint of every machine is satisfied. The GAP is a classic optimization problem and has been studied extensively from the algorithmic perspective. Dughmi and Ghosh [Dughmi S, Ghosh A (201...
-
作者：Li, Chenxu
作者单位：Peking University
摘要：Enlightened by the theory of Watanabe [Watanabe S (1987) Analysis of Wiener functionals (Malliavin calculus) and its applications to heat kernels. Ann. Probab. 15:1-39] for analyzing generalized random variables and its further development in Yoshida [Yoshida N (1992a) Asymptotic expansions for statistics related to small diffusions. J. Japan Statist. Soc. 22: 139-159], Takahashi [Takahashi A (1995) Essays on the valuation problems of contingent claims. Ph.D. thesis, Haas School of Business, U...
-
作者：Mordukhovich, Boris S.; Nghia, T. T. A.
作者单位：Wayne State University
摘要：This paper is devoted to the study of general nonsmooth problems of cone-constrained optimization (or conic programming) important for various aspects of optimization theory and applications. Based on advanced constructions and techniques of variational analysis and generalized differentiation, we derive new necessary optimality conditions (in both exact and fuzzy forms) for nonsmooth conic programs, establish characterizations of well-posedness for cone-constrained systems, and develop new ap...
-
作者：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...
-
作者：Van Foreest, Nicky D.; Wijngaard, Jacob
作者单位：University of Groningen
摘要：In this paper, we consider a single-item, one-machine production-inventory system with compound Poisson demand. The production facility may be on or off. While on, the production rate is constant, and, while off, the production rate is zero. System costs consist of switching costs and inventory and backlogging costs. We provide conditions when (s 1 S)-policies are optimal under the long-run average expected cost criterion. These conditions are met in particular, but not necessarily, when the i...
-
作者：Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
作者单位：William & Mary; Cornell University
摘要：Determining the precise integrality gap for the subtour linear programming (LP) relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [Boyd S, Carr R (2011) Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8:525-539. Prior version accessed June 27, 2011, http://www.site.uottawa.ca/(similar ...
-
作者：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...
