-
作者：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...
-
作者：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...
-
作者：Grandits, Peter
作者单位：Technische Universitat Wien
摘要：We give an algorithmic solution of the optimal consumption problem sup(C) integral([0, tau]) e(-beta t) dC(t), where C-t denotes the accumulated consumption until time t, and tau denotes the time of ruin. Moreover, the endowment process X-t is modeled by X-t = x + integral(t)(0) mu(X-s) ds - C-t. We solve the problem by showing that the function provided by the algorithm solves the Hamilton-Jacobi (HJ) equation in a viscosity sense and that the same is true for the value function of the proble...
-
作者：Seel, Christian; Strack, Philipp
作者单位：Maastricht University; University of California System; University of California Berkeley
摘要：This paper introduces a class of contest models in which each player decides when to stop a privately observed Brownian motion with drift and incurs costs depending on his stopping time. The player who stops his process at the highest value wins a prize. We prove existence and uniqueness of a Nash equilibrium outcome and derive the equilibrium distribution in closed form. As the variance tends to zero, the equilibrium outcome converges to the symmetric equilibrium of an all-pay auction. For tw...
-
作者：Friggstad, Zachary; Gupta, Anupam; Singh, Mohit
作者单位：University of Alberta; Carnegie Mellon University; Microsoft
摘要：The asymmetric traveling salesperson path problem (ATSPP) is one where, given an asymmetric metric space (V, d) with specified vertices s and t, the goal is to find an s-t path of minimum length that passes through all the vertices in V. This problem is closely related to the asymmetric TSP (ATSP), which seeks to find a tour (instead of an s-t path) visiting all the nodes: for ATSP, a rho-approximation guarantee implies an O(rho)-approximation for ATSPP. However, no such connection is known fo...
-
作者：von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science
摘要：We consider a sequential inspection game where an inspector uses a limited number of inspections over a larger number of time periods to detect a violation (an illegal act) of an inspectee. Compared with earlier models, we allow varying rewards to the inspectee for successful violations. As one possible example, the most valuable reward may be the completion of a sequence of thefts of nuclear material needed to build a nuclear bomb. The inspectee can observe the inspector, but the inspector ca...
-
作者：Adamczyk, Marek; Sviridenko, Maxim; Ward, Justin
作者单位：Sapienza University Rome; Yahoo! Inc; University of Warwick
摘要：In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only ...
