-
作者：Kunnumkal, Sumit; Talluri, Kalyan
作者单位：Indian School of Business (ISB); Imperial College London
摘要：The network revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale products use multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationally intractable because of an exponentially large state space, and a number of heuristics have been proposed to approximate its value function. In this paper we show that the piecewise-linear approximation to the network RM dynamic program is tractable; speci...
-
作者：Mucha, Marcin; Sviridenko, Maxim
作者单位：University of Warsaw; Yahoo! Inc; University of Warwick
摘要：In this paper, we study the classical no-wait flowshop scheduling problem with makespan objective (F vertical bar no-wait vertical bar C-max in the standard three-field notation). This problem is well known to be a special case of the asymmetric traveling salesman problem (ATSP) and as such has an approximation algorithm with logarithmic performance guarantee. In this work, we show a reverse connection, we show that any polynomial time alpha-approximation algorithm for the no-wait flowshop sch...
-
作者：Lam, Henry
作者单位：University of Michigan System; University of Michigan
摘要：We study a worst-case approach to measure the sensitivity to model misspecification in the performance analysis of stochastic systems. The situation of interest is when only minimal parametric information is available on the form of the true model. Under this setting, we post optimization programs that compute the worst-case performance measures, subject to constraints on the amount of model misspecification measured by Kullback-Leibler divergence. Our main contribution is the development of i...
-
作者：Huang, Junfei; Zhang, Hanqin; Zhang, Jiheng
作者单位：Chinese University of Hong Kong; National University of Singapore; Hong Kong University of Science & Technology
摘要：We propose a unified approach to establishing diffusion approximations for queues with impatient customers within a general framework of scaling customer patience time. The approach consists of two steps. The first step is to show that the diffusion-scaled abandonment process is asymptotically close to a function of the diffusion-scaled queue length process under appropriate conditions. The second step is to construct a continuous mapping not only to characterize the system dynamics using the ...
-
作者：Chakrabarty, Deeparnab; Swamy, Chaitanya
作者单位：Microsoft; Microsoft India; University of Waterloo
摘要：We introduce a problem that is a common generalization of the uncapacitated facility location (UFL) and minimum latency (ML) problems, where facilities not only need to be opened to serve clients, but also need to be sequentially activated before they can provide service. This abstracts a setting where inventory demanded by customers needs to be stocked or replenished at facilities from a depot or warehouse. Formally, we are given a set F of n facilities with facility-opening costs, a set D of...
-
作者：Dayanik, Savas; Sezer, Semih O.
作者单位：Ihsan Dogramaci Bilkent University; Ihsan Dogramaci Bilkent University; Sabanci University
摘要：We consider a centralized multisensor online quickest disorder detection problem where the observation from each sensor is a Wiener process gaining a constant drift at a common unobservable disorder time. The objective is to detect the disorder time as quickly as possible with small probability of false alarms. Unlike the earlier work on multisensor change detection problems, we assume that the observer can apply a sequential sensor installation policy. At any time before a disorder alarm is r...
-
作者：Buchbinder, Niv; Chen, Shahar; Naor, Joseph (Seffi); Shamir, Ohad
作者单位：Tel Aviv University; Technion Israel Institute of Technology; Weizmann Institute of Science
摘要：Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learni...
-
作者：Cui, Leon; Tezcan, Tolga
作者单位：State University of New York (SUNY) System; Binghamton University, SUNY; University of London; London Business School
摘要：We study a queueing model of customer service chat systems. A unique feature of these queueing systems is that a single agent can serve multiple customers simultaneously. We prove the convergence of the queueing process to different diffusion processes in a many-server heavy-traffic regime in three different cases. Using this result, we are able to offer approximations for the steady-state performance measures such as the number of customers in the system, the abandonment probability, and the ...
-
作者：Kruk, Lukasz; Sokolowska, Ewa
作者单位：Maria Curie-Sklodowska University
摘要：A single queueing station serving K input streams with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served by the Shortest Remaining Processing Time policy. In the case of a tie, the first-in, first-out policy is utilized. We analyze a fluid model for the evolution of a measure-valued state descriptor of this system, with particular emphasis on its limiting behavior in the critical case as time gets large. We also...
-
作者：Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：We study disjunctive conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone, or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that, under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient to describe the convex hull. We focus on the properties of K-minimal inequalities by establishing algebraic nece...
