-
作者：Hochbaum, Dorit S.; Levin, Asaf; Rao, Xu
作者单位：Technion Israel Institute of Technology
摘要：Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parame...
-
作者：Tse, Alex S. L.; Zheng, Harry
作者单位：University of London; University College London; Imperial College London
摘要：We present a continuous-time portfolio selection problem faced by an agent with S-shaped preference who maximizes the utilities derived from the portfolio's periodic performance over an infinite horizon. The periodic reward structure creates subtle incentive distortion. In some cases, local risk aversion is induced, which discourages the agent from risk taking in the extreme bad states of the world. In some other cases, eventual ruin of the portfolio is inevitable, and the agent underinvests i...
-
作者：Ingolfsson, Armann; Mandelbaum, Avishai; Schultz, Kenneth; Yom-Tov, Galit B.
作者单位：University of Alberta; Technion Israel Institute of Technology
-
作者：Asadpour, Arash; Niazadeh, Rad; Saberi, Amin; Shameli, Ali
作者单位：City University of New York (CUNY) System; Baruch College (CUNY); University of Chicago; Stanford University
摘要：We study a submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first k items in the list for a k chosen at random from a given distribution and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engagement of the shopper defined as the probability of purchase. This problem gives rise to a less-studied v...
-
作者：Aouad, Ali; Segev, Danny
作者单位：University of London; London Business School; Tel Aviv University
摘要：We study the incremental knapsack problem, where one wishes to sequentially pack items into a knapsack whose capacity expands over a finite planning horizon, with the objective of maximizing time-averaged profits. Although various approximation algorithms were developed under mitigating structural assumptions, obtaining nontrivial performance guarantees for this problem in its utmost generality has remained an open question thus far. In this paper, we devise a polynomial-time approximation sch...
-
作者：Hathaway, Brett A.; Kagan, Evgeny; Dada, Maqbool
作者单位：Johns Hopkins University
摘要：In many service encounters, frontline workers ( often referred to as gatekeepers) have the discretion to attempt to resolve a customer request or to transfer the customer to an expert service provider. Motivated by an incentive redesign at a call center of a midsize U.S.-based bank, we formulate and solve an analytical model of the gate-keeper's transfer response to different incentive schemes and congestion levels. We then test several model predictions experimentally. Our experiments show th...
-
作者：Liang, Jinpeng; Lyu, Guodong; Teo, Chung-Piaw; Gao, Ziyou
作者单位：Dalian Maritime University; Hong Kong University of Science & Technology; National University of Singapore; National University of Singapore; Beijing Jiaotong University
摘要：Crowd management during peak commuting hours is a key challenge facing oversaturated metro systems worldwide, which results in serious safety concerns and uneven service experience for commuters on different origin-destination (o-d) pairs. This paper develops realtime passenger flow control policies to manage the inflow of crowds at each station, to optimize the total load carried or revenue earned (efficiency), and to ensure that adequate service is provided to passengers on each o-d pair (fa...
-
作者：Talluri, Kalyan; Tsoukalasb, Angelos
作者单位：Imperial College London; Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC
摘要：Professional service firms (PSFs) such as management consulting, law, accounting, investment banking, architecture, advertising, and home-repair companies provide services for complicated turnkey projects. A firm bids for a project and, if successful in the bid, assigns employees to work on the project. We formulate this as a revenue management problem under two assumptions: a quality-revelation setup, where the employees that would be assigned to the project are committed ex ante, as part of ...
-
作者：Hamidi, Nima; Bayati, Mohsen
作者单位：Stanford University; Stanford University
摘要：In this note, we introduce a general version of the well-known elliptical potential lemma that is a widely used technique in the analysis of algorithms in sequential learning and decision-making problems. We consider a stochastic linear bandit setting where decision makers sequentially choose among a set of given actions, observe their noisy rewards, and aim to maximize their cumulative expected reward over a decision-making horizon. The elliptical potential lemma is a key tool for quantifying...
-
作者：Spliet, Remy
作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
摘要：State-of-the-art exact algorithms for vehicle routing problems are branch-price-and-cut algorithms that make use of a set partitioning formulation. Only exponential time algo-rithms are known for the corresponding pricing problem. In this technical note, it is proven that the pricing problem is strongly NP-hard for various vehicle routing problems. This justi-fies the common use of route relaxations that modify the set partitioning formulation with the aim to allow pseudopolynomial pricing alg...
