-
作者：Yu, Huizhen; Bertsekas, Dimitri P.
作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
摘要：We consider the average cost problem for partially observable Markov decision processes (POMDP) with finite state, observation, and control spaces. We prove that there exists an E-optimal finite-state controller (FSC) functionally independent of initial distributions for any epsilon > 0, under the assumption that the optimal liminf average cost function of the POMDP is constant. As part of our proof, we establish that if the optimal liminf average cost function is constant, then the optimal li...
-
作者：Glasserman, Paul; Juneja, Sandeep
作者单位：Columbia University; Tata Institute of Fundamental Research (TIFR)
摘要：Successful efficient rare-event simulation typically involves using importance sampling tailored to a specific rare event. However, in applications one may be interested in simultaneous estimation of many probabilities or even an entire distribution. In this paper, we address this issue in a simple but fundamental setting. Specifically, we consider the problem of efficient estimation of the probabilities P(S-n >= na) for large n, for all a lying in an interval A, where S-n denotes the sum of n...
-
作者：Caprara, Alberto
作者单位：University of Bologna
摘要：We consider the d-dimensional bin-packing problem, the most relevant generalization of classical bin packing, and show a general result about the asymptotic worst-case ratio of a wide class of approximation algorithms that construct solutions in d stages, containing many heuristics previously considered in the literature. Moreover, we give the exact value of the asymptotic worst-case ratio between the optimal solution and the best solution obtainable by packing the items in d stages, showing h...
-
作者：Montrucchio, Luigi; Semeraro, Patrizia
作者单位：Collegio Carlo Alberto; University of Turin; University of Turin
摘要：A definition of setwise differentiability for set functions is given through refining the partitions of sets. Such a construction is closely related to the one proposed by Rosenmuller [Rosenmuller, J. 1977. Extreme Games and Their Solutions. Springer-Verlag, Berlin], Epstein [Epstein, L. 1999. A definition of uncertainty aversion. Rev. Econom. Stud. 66 579-608], and Epstein and Marinacci [Epstein, L., M. Marinacci. 2001. The core of large differentiable TU games. J Econom. Theory 100 235-273]....
-
作者：Jennings, Otis B.
作者单位：Duke University
摘要：We consider two serial single-server stations in heavy traffic. There are two job types: All jobs visit station I and then station 2. Station 1 processes jobs in an exhaustive service or gated service fashion; station 2 uses an arbitrary nonidling service discipline. Neither station incurs switchover delays. We prove two heavy-traffic limit theorems (HTLT) for the diffusion-scaled, two-dimensional total workload process: one for when the first station implements exhaustive service and the othe...
-
作者：Belloni, Alexandre
作者单位：Duke University
摘要：where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and vertical bar vertical bar.vertical bar vertical bar is any norm. We also develop connections between these densities and geometric properties of K such as diameter, width of the recession cone, and others. Since f(t) is log-concave only if p >= 1, this framework also covers nonlog-concave densities. Moreover, we establish a new set inclusion characterization for convex sets. This leads to a new conc...
-
作者：Oriolo, Gianpaolo
作者单位：University of Rome Tor Vergata
摘要：A traffic matrix D-1 dominates a traffic matrix D-2 if any capacity reservation supporting D-1 supports D-2 as well. We prove that D-1 dominates D-2 if and only if D-1, considered as a capacity reservation, supports D-2. We show several generalizations of this result.
-
作者：Ward, Amy R.; Kumar, Sunil
作者单位：University of Southern California; Stanford University
摘要：We consider a GI/GI/1 queue with impatient customers in heavy traffic. We use the solution of an approximating singular diffusion control problem to construct an admission control policy for the queue. The approximating control problem does not admit a so-called pathwise solution. Hence, the resulting admission control policy depends on second-moment data. We prove asymptotic optimality of the constructed policy using weak-convergence methods.
-
作者：Dey, Santanu S.; Richard, Jean-Philippe P.
作者单位：Purdue University System; Purdue University
摘要：In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet of 2DMIIGP. We then present two different constructions that yield the first known families of facet-defining inequalities for 2DMIIGP. The first construction uses valid inequalities of the one...
-
作者：DeMiguel, Victor; Nogales, Francisco J.
作者单位：University of London; London Business School; Universidad Carlos III de Madrid
摘要：We study two different decomposition algorithms for the general (nonconvex) partially separable nonlinear program (PSP): bilevel decomposition algorithms (BDAs) and Schur interior-point methods (SIPMs). BDAs solve the problem by breaking it into a master problem and a set of independent subproblems, forming a type of bilevel program. SIPMs, on the other hand, apply an interior-point technique to solve the problem in its original (integrated) form, but then use a Schur complement approach to so...
