-
作者：Reed, Josh; Shaki, Yair
作者单位：New York University; Technion Israel Institute of Technology
摘要：We consider the G / GI / N queue with multiple server pools, each possessing a pool-specific service time distribution. The class of nonidling routing policies that we consider are referred to as u-greedy policies. These policies route incoming customers to the server pool with the longest weighted cumulative idle time to equitably spread incoming work amongst the server pools in the system. Our first set of results demonstrates that asymptotically in the Halfin-Whitt regime and under any u-gr...
-
作者：Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S.; Kaibel, Volker
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidad Catolica de Chile; Otto von Guericke University
摘要：In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations w...
-
作者：Venel, Xavier
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Humanities & Social Sciences (INSHS); heSam Universite; Universite Pantheon-Sorbonne
摘要：We are interested in the convergence of the value of n-stage games as n goes to infinity and the existence of the uniform value in stochastic games with a general set of states and finite sets of actions where the transition is commutative. This means that playing an action profile a(1) followed by an action profile a(2), leads to the same distribution on states as playing first the action profile a(2) and then a(1). For example, absorbing games can be reformulated as commutative stochastic ga...
-
作者：Perchet, Vianney; Quincampoix, Marc
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite; Universite Paris Cite; Universite de Bretagne Occidentale; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：We represent any repeated game with partial monitoring as an abstract repeated game with full monitoring where outcomes are probability measures, to be interpreted as the maximal information the players can obtain in the original game. One of our objectives is to define and generalize Blackwell's approachability theory in this space of probability measures. We characterize approachable sets with, as usual, a simple and complete formulation for convex sets. Translated back into the original gam...
-
作者：Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas
作者单位：Johns Hopkins University; University of Chicago
摘要：Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs, which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to s...
-
作者：Gensbittel, Fabien
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole
摘要：This work is devoted to extend several asymptotic results concerning repeated games with incomplete information on one side. The model we consider is a generalization of the classical model of Aumann and Maschler (Aumann et al. [Aumann RJ, Maschler M, Stearns RE (1995) Repeated Games with Incomplete Information (MIT Press, Cambridge, MA)]) to infinite action spaces and partial information. We prove an extension of the classical Cav(u) Theorem in this model for both the lower and upper value fu...
-
作者：Li, Min; Yuan, Xiaoming
作者单位：Southeast University - China; Hong Kong Baptist University
摘要：Recently, a strictly contractive Peaceman-Rachford splitting method (PRSM) was proposed for a separable convex minimization model whose variables are subject to some linear constraints and two additional generic constraints. In general, the strictly contractive PRSM requires to solve two constrained minimization subproblems at each iteration. In this paper, we consider the case where the additional constraints on variables are positive orthants and apply the well-developed logarithmic-quadrati...
-
作者：Boxma, Onno; Perry, David; Zacks, Shelley
作者单位：Eindhoven University of Technology; Eindhoven University of Technology; University of Haifa; State University of New York (SUNY) System; Binghamton University, SUNY
摘要：We consider a stochastic fluid EOQ-type model with demand rates operating in a two-state random environment. This environment alternates between exponentially distributed periods of high demand and generally distributed periods of low demand. The inventory level starts at some level q, and decreases linearly at rate, beta(H) during the periods of high demand, and at rate, beta(L) < beta(H) at periods of low demand. Refilling of the inventory level to level q is required when the first of two e...
-
作者：Conforti, Michele; Cornuejols, Gerard; Daniilidis, Aris; Lemarechal, Claude; Malick, Jerome
作者单位：University of Padua; Carnegie Mellon University; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS)
摘要：We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (CGF) and we develop a formal theory for them, largely based on convex analysis. They are...
-
作者：Yu, Huizhen; Bertsekas, Dimitri P.
作者单位：University of Alberta; Massachusetts Institute of Technology (MIT)
摘要：We consider stochastic optimal control models with Borel spaces and universally measurable policies. For such models the standard policy iteration is known to have difficult measurability issues and cannot be carried out in general. We present a mixed value and policy iteration method that circumvents this difficulty. The method allows the use of stationary policies in computing the optimal cost function in a manner that resembles policy iteration. It can also be used to address similar diffic...
