-
作者：Aghajani, Reza; Ramanan, Kavita
作者单位：University of California System; University of California San Diego; Brown University
摘要：We consider the so-called GI/GI/N queue, in which a stream of jobs with independent and identically distributed service times arrive as a renewal process to a common queue that is served by N identical parallel servers in a first-come, first-served manner. We introduce a new representation for the state of the system and, under suitable conditions on the service and interarrival distributions, establish convergence of the corresponding sequence of centered and scaled stationary distributions i...
-
作者：Wang, Mengdi
作者单位：Princeton University
摘要：We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted-reward and average-reward Markov decision problems. By leveraging the value-policy duality, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an f-optimal policy using nearly linear runtime in the worst case for a fixed value of the discount factor. When the Markov decision process is ergodic and speci...
-
作者：Solan, Eilon; Solan, Omri N.
作者单位：Tel Aviv University
摘要：We prove that every multiplayer quitting game admits a sunspot epsilon-equilibrium for every epsilon> 0, that is, an e-equilibrium in an extended game in which the players observe a public signal at every stage. We also prove that, if a certain matrix that is derived from the payoffs in the game is not a Q-matrix in the sense of linear complementarity problems, then the game admits a uniform epsilon-equilibrium for every epsilon > 0.
-
作者：Li, Shi
作者单位：State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：We study the nonuniform capacitated multi-item lot-sizing problem. In this problem, there is a set of demands over a planning horizon of T discrete time periods, and all demands must be satisfied on time. We can place an order at the beginning of each period s, incurring an ordering cost K-s. In this order, we can order up to C-s units of products. On the other hand, carrying inventory from time to time incurs an inventory holding cost. The goal of the problem is to find a feasible solution th...
-
作者：Pender, Jamol; Rand, Richard; Wesson, Elizabeth
作者单位：Cornell University; Cornell University; Cornell University
摘要：Many service systems provide queue length information to customers, thereby allowing customers to choose among many options of service. However, queue length information is often delayed, and it is often not provided in real time. Recent work by Dong et al. [Dong J, Yom-Tov E, Yom-Tov GB (2018) The impact of delay announcements on hospital network coordination and waiting times. Management Sci. 65(5):1969-1994.] explores the impact of these delays in an empirical study in U.S. hospitals. Work ...
-
作者：Anselmi, Jonatha; Dufour, Francois
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Universite de Bordeaux
摘要：In multiserver distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as a load balancer. A fundamental problem consists in designing a load-balancing algorithm that minimizes the delays experienced by jobs. During the last two decades, the power-of-d-choice algorithm, based on the idea of dispatching each job to the least loaded server out of d servers randomly sampled at the arrival of the job itself, has emerged a...
-
作者：Bot, Radu Ioan; Dang-Khoa Nguyen
作者单位：University of Vienna; Babes Bolyai University from Cluj
摘要：We propose two numerical algorithms in the fully nonconvex setting for the minimization of the sum of a smooth function and the composition of a nonsmooth function with a linear operator. The iterative schemes are formulated in the spirit of the proximal alternating direction method of multipliers and its linearized variant, respectively. The proximal terms are introduced via variable metrics, a fact that allows us to derive new proximal splitting algorithms for nonconvex structured optimizati...
-
作者：Eshragh, Ali; Filar, Jerzy A.; Kalinowski, Thomas; Mohammadian, Sogol
作者单位：University of Newcastle; University of Queensland; University of New England
摘要：We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph G and determine the expected numbers of different types of feasible bases when the und...
-
作者：Budhiraja, Amarjit; Johnson, Dane
作者单位：University of North Carolina; University of North Carolina Chapel Hill
摘要：We consider resource sharing networks of the form introduced in work of Massoulie and Roberts as models for Internet flows. The goal is to study the open problem, formulated in Harrison et al. (2014) [Harrison JM, Mandayam C, Shah D, Yang Y (2014) Resource sharing networks: Overview and an open problem. Stochastic Systems 4(2):524-555.], of constructing simple form rate-allocation policies for broad families of resource sharing networks with associated costs converging to the hierarchical gree...
-
作者：Segal-Halevi, Erel; Nitzan, Shmuel; Hassidim, Avinatan; Aumann, Yonatan
作者单位：Ariel University; Bar Ilan University
摘要：Classic cake-cutting algorithms enable people with different preferences to divide among them a heterogeneous resource (cake) such that the resulting division is fair according to each agent's individual preferences. However, these algorithms either ignore the geometry of the resource altogether or assume it is one-dimensional. In practice, it is often required to divide multidimensional resources, such as land estates or advertisement spaces in print or electronic media. In such cases, the ge...
