-
作者：Wang, Mengdi; Bertsekas, Dimitri P.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x(k)} that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditio...
-
作者：Molinaro, Marco; Ravi, R.
作者单位：Carnegie Mellon University
摘要：We consider packing linear programs with m rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive to obtain a feasible solution maximizing the expected reward. Previous (1 - epsilon)-competitive algorithms require the right-hand side of the linear program to be Omega((m/epsilon(2))log(n/epsilon)), a bound that worsens with the number of column...
-
作者：Buchbinder, Niv; Jain, Kamal; Singh, Mohit
作者单位：Tel Aviv University; eBay Inc.; Microsoft
摘要：In the classical secretary problem an employer would like to choose the best candidate among n competing candidates that arrive in a random order. In each iteration, one candidate's rank vis-a-vis previously arrived candidates is revealed and the employer makes an irrevocable decision about her selection. This basic concept of n elements arriving in a random order and irrevocable decisions made by an algorithm have been explored extensively over the years, and used for modeling the behavior of...
-
作者：Gurvich, Itai
作者单位：Northwestern University
摘要：A class of stochastic processes known as semi-martingale reflecting Brownian motions (SRBMs) is often used to approximate the dynamics of heavily loaded queueing networks. In two influential papers, Bramson [Bramson M (1998) State space collapse with applications to heavy-traffic limits for multiclass queueing networks. Queueing Systems 30: 89-148] and Williams [Williams RJ (1998b) Diffusion approximations for open multiclass queueuing networks: Sufficient conditions involving state space coll...
-
作者：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...
-
作者：Weerasinghe, Ananda
作者单位：Iowa State University
摘要：We consider a sequence of many-server queueing systems with impatient customers of the type G/M/n + GI in heavy traffic. This sequence is indexed by n, where the parameter n represents the number of servers in the nth system. The state process is considered to be the diffusion-scaled total customer count in the system and the service rate is a state-dependent perturbation of a given basic service rate mu(0) > 0. When the system is critically loaded in the Halfin-Whitt heavy traffic regime, we ...
-
作者：Hirai, Hiroshi
作者单位：University of Tokyo
摘要：We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1/12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanov's conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multifl...
-
作者：Audibert, Jean-Yves; Bubeck, Sebastien; Lugosi, Gabor
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Inria; Princeton University; ICREA; Pompeu Fabra University
摘要：We address online linear optimization problems when the possible actions of the decision maker are represented by binary vectors. The regret of the decision maker is the difference between her realized loss and the minimal loss she would have achieved by picking, in hindsight, the best possible action. Our goal is to understand the magnitude of the best possible (minimax) regret. We study the problem under three different assumptions for the feedback the decision maker receives: full informati...
-
作者：Baeuerle, Nicole; Rieder, Ulrich
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; Ulm University
摘要：We investigate the problem of minimizing a certainty equivalent of the total or discounted cost over a finite and an infinite horizon that is generated by a Markov decision process (MDP). In contrast to a risk-neutral decision maker this optimization criterion takes the variability of the cost into account. It contains as a special case the classical risk-sensitive optimization criterion with an exponential utility. We show that this optimization problem can be solved by an ordinary MDP with e...
