-
作者：Rutten, Daan; Mukherjeea, Debankur
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Consider a system with N identical single-server queues and a number of task types, where each server is able to process only a small subset of possible task types. Arriving tasks select d >= 2 random compatible servers and join the shortest queue among them. The compatibility constraints are captured by a fixed bipartite graph between the servers and the task types. When the graph is complete bipartite, the mean-field approximation is accurate. However, such dense compatibility graphs are inf...
-
作者：Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
作者单位：Brown University; Massachusetts Institute of Technology (MIT); University of Southern California; Cornell University
摘要：There is an error in our paper [Paul A, Freund D, Ferber A, Shmoys DB, William-son DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576-590]. In that paper, we consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the probl...
-
作者：Kara, Ali Devran; Yuksel, Serdar
作者单位：University of Michigan System; University of Michigan; Queens University - Canada
摘要：In this paper, for partially observed Markov decision problems (POMDPs), we provide the convergence of a Q learning algorithm for control policies using a finite history of past observations and control actions, and consequentially, we establish near optimality of such limit Q functions under explicit filter stability conditions. We present explicit error bounds relating the approximation error to the length of the finite history window. We establish the convergence of such Q learning iteratio...
-
作者：Ahmadi, Amir Ali; Dibek, Cemil; Hall, Georgina
作者单位：Princeton University; INSEAD Business School
摘要：We study separable plus quadratic (SPQ) polynomials, that is, polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial and (ii) a sum of squares. We establish that the answer to question (i) is positive for univari...
-
作者：Zhao, Renbo
作者单位：University of Iowa
摘要：We propose a primal-dual smoothing framework for finding a near-stationary point of a class of nonsmooth nonconvex optimization problems with max-structure. We analyze the primal and dual gradient complexities of the framework via two approaches, that is, the dual-then-primal and primal-the-dual smoothing approaches. Our framework improves the best-known oracle complexities of the existing method, even in the restricted problem setting. As an important part of our framework, we propose a first...
-
作者：Balseiro, Santiago; Golrezaei, Negin; Mahdian, Mohammad; Mirrokni, Vahab; Schneider, Jon
作者单位：Columbia University; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
摘要：In the classic contextual bandits problem, in each round t, a learner observes some context c, chooses some action i to perform, and receives some reward r(i,t)(c). We consider the variant of this problem in which in addition to receiving the reward r(i,t)(c), the learner also learns the values of r(i,t)(c ') for some other contexts c ' in set Oi(c), that is, the rewards that would be achieved by performing that action under different contexts c 'is an element of O-i(c). This variant arises in...
-
作者：Kanoria, Yash; Lobel, Ilan; Lu, Jiaqi
作者单位：Columbia University; New York University; The Chinese University of Hong Kong, Shenzhen
摘要：We introduce a novel stochastic control model for the problem of a service firm interacting over time with one of its customers who probabilistically churns depending on the customer's satisfaction. The firm has two service modes available, and they determine the drift and volatility of the Brownian reward process. The firm's objective is to maximize the rewards generated over the customer's lifetime. Meanwhile, the customer might churn probabilistically if the customer's satisfaction, modeled...
-
作者：Glover, Kristoffer; Peskir, Goran
作者单位：University of Technology Sydney; University of Manchester
摘要：Consider an Ornstein-Uhlenbeck process that initially reverts to zero at a known mean-reversion rate & beta;0, and then after some random/unobservable time, this mean reversion rate is changed to & beta;1. Assuming that the process is observed in real time, the problem is to detect when exactly this change occurs as accurately as possible. We solve this problem in the most uncertain scenario when the random/unobservable time is (i) exponentially distributed and (ii) independent from the proces...
-
作者：Cerny, Ales; Czichowsky, Christoph; Kallsen, Jan
作者单位：City St Georges, University of London; University of London; London School Economics & Political Science; University of Kiel
摘要：The paper investigates quadratic hedging in a semimartingale market that does not necessarily contain a risk-free asset. An equivalence result for hedging with and without numeraire change is established. This permits direct computation of the optimal strategy without choosing a reference asset and/or performing a numeraire change. New explicit expressions for optimal strategies are obtained, featuring the use of oblique projections that provide unified treatment of the case with and without a...
-
作者：Cheng, Yukun; Deng, Xiaotie; Qi, Qi; Yan, Xiang
作者单位：Suzhou University of Science & Technology; Peking University; Renmin University of China; Huawei Technologies
摘要：We consider a sharing economy over a network in which each vertex agent allocates resources to its neighbors in response to their contributions. General equilibrium theory can be applied here to solve the problem of deciding how to fairly and efficiently allocate resources among agents as resource sharing over the network can be modeled as a pure exchange economy. It is known that proportional sharing dynamics converges to a market equilibrium solution. We are particularly interested in propor...
