-
作者：Glazebrook, K. D.; Minty, R.
作者单位：Lancaster University
摘要：We generalise classical multiarmed bandits to allow for the distribution of a (fixed amount of a) divisible resource among the constituent bandits at each decision point. Bandit activation consumes amounts of the available resource, which may vary by bandit and state. Any collection of bandits may be activated at any decision epoch, provided they do not consume more resource than is available. We propose suitable bandit indices that reduce to those proposed by Gittins [Gittins, J. C. 1979. Ban...
-
作者：Cominetti, Roberto; Piazza, Adriana
作者单位：Universidad de Chile; Universidad de Chile
摘要：We study the long-term behavior of the optimal harvesting policies for a mixed forest composed by multiple species of different maturity ages. This model is a prototype for the exploitation of a finite resource such as land or space, which can be allocated to different activities that produce their revenue after certain delays at which the resource is liberated for reuse. We prove the existence and uniqueness of a sustainable state, and we discuss the conditions under which an optimal trajecto...
-
作者：Halman, Nir; Klabjan, Diego; Mostagir, Mohamed; Orlin, Jim; Simchi-Levi, David
作者单位：Massachusetts Institute of Technology (MIT); Hebrew University of Jerusalem; Northwestern University; California Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：The single-item stochastic inventory control problem is to find an inventory replenishment policy in the presence of independent discrete stochastic demands under periodic review and finite time horizon. In this paper, we prove that this problem is intractable and design for it a fully polynomial-time approximation scheme.
-
作者：Mertens, Jean-Francois; Neyman, Abraham; Rosenberg, Dinah
作者单位：Universite Catholique Louvain; Hebrew University of Jerusalem; Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); Universite Paris 13; heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We prove that games with absorbing states with compact action sets have a value.
-
作者：Nascimento, Juliana M.; Powell, Warren B.
作者单位：Princeton University
摘要：We consider a multistage asset acquisition problem where assets are purchased now, at a price that varies randomly over time, to be used to satisfy a random demand at a particular point in time in the future. We provide a rare proof of convergence for an approximate dynamic programming algorithm using pure exploitation, where the states we visit depend on the decisions produced by solving the approximate problem. The resulting algorithm does not require knowing the probability distribution of ...
-
作者：Galluccio, Anna; Gentile, Claudio; Ventura, Paolo
作者单位：Consiglio Nazionale delle Ricerche (CNR)
摘要：Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB (H) and STAB (H-e), where He is the graph obtained from H by subdividing the edge e. We also introduce the class of G-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-whee...
-
作者：Zadorojniy, Alexander; Even, Guy; Shwartz, Adam
作者单位：Tel Aviv University; Technion Israel Institute of Technology
摘要：We consider the problem of computing optimal policies of finite-state finite-action Markov decision processes (MDPs). A reduction to a continuum of constrained MDPs (CMDPs) is presented such that the optimal policies for these CMDPs constitute a path in a graph defined over the deterministic policies. This path contains, in particular, an optimal policy of the original MDP. We present an algorithm based on this new approach that finds this path, and thus an optimal policy. In the general case,...
-
作者：Randhawa, Ramandeep S.; Kumar, Sunil
作者单位：University of Texas System; University of Texas Austin; Stanford University
摘要：We study a multiserver loss system with two kinds of customers: subscribers and infrequent users. We model the infrequent users' requests for service by a Poisson process. However, noting that the Poisson process is unable to capture repeated interactions as well as retrials, we propose a Markovian on-off-hold model for the subscribers' requests for service that takes into account retrials by subscribers denied service. We analyze this system in an asymptotic regime where the number of subscri...
-
作者：Blanquero, Rafael; Carrizosa, Emilio; Hansen, Pierre
作者单位：University of Sevilla; Universite de Montreal; Universite de Montreal; HEC Montreal
摘要：We address the problem of locating objects in the plane such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries. Given a set of points, we seek the rotation and translation for such an object optimizing a very general performance measure, which includes as a particular case the classical objectives in semi-obnoxious facility location. In general, the above-mentioned model yields a global optimization problem, whose resolution is dealt with using d...
-
作者：Freund, Robert M.; Vera, Jorge R.
作者单位：Massachusetts Institute of Technology (MIT); Pontificia Universidad Catolica de Chile
摘要：Consider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e. g., no domain ball containing or intersecting the set, etc.). The authors' interest in this problem stems from fundamental issues involving the interplay of (i) the computational complexity of computing a point in the set, (ii) the geometry of the set, and (iii) the stability or conditioning of the set under perturbation. Under suitable definitions...
