-
作者：Rath, Sandeep; Rajaram, Kumar; Hudson, Mark E.; Mahajan, Aman
作者单位：Indian School of Business (ISB); University of California System; University of California Los Angeles; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：This paper presents the development, validation, and implementation of a datadriven optimization model designed to dynamically plan the assignment of anesthesiologists across multiple hospital locations within a large multispecialty healthcare system. We formulate the problem as a multistage robust mixed-integer program incorporating on-call flexibility to address demand uncertainty. In the first stage, anesthesiologists are assigned to specific locations or an on-call pool several weeks befor...
-
作者：Fan, Jianqing; Lou, Zhipeng; Wang, Weichen; Yu, Mengxin
作者单位：Princeton University; University of California System; University of California San Diego; University of Hong Kong; Washington University (WUSTL)
摘要：This paper studies the performance of the spectral method in the estimation and uncertainty quantification of the unobserved preference scores of compared entities in a general and more realistic setup. Specifically, the comparison graph consists of hyperedges of possible heterogeneous sizes, and the number of comparisons can be as low as one for a given hyper-edge. Such a setting is pervasive in real applications, circumventing the need to specify the graph randomness and the restrictive homo...
-
作者：Soh, Seung Bum; Gurvich, Itai
作者单位：Yonsei University; Northwestern University
摘要：Staffing problems are often formulated as satisfization problems, in which the cost of servers is minimized subject to quality of service constraints. These constraints indirectly capture customers' disutility from waiting or, at least, its structure. For the problem of staffing a single-class M/M/N queue with an average speed of answer (ASA) constraint, any work-conserving policy is optimal; the problem's formulation is, in that sense, ambiguous. One optimal solution is consistent with convex...
-
作者：Udwani, Rajan
作者单位：University of California System; University of California Berkeley
摘要：We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that a nonadaptive Greedy algorithm, which is oblivious to the realization of these stochastic elements, achieves the best possible competitive ratio among all polynomial-time algorithms, including adaptive ones, unless NP = RP. This result holds even when the objective function is not submodular but instead satisfies the...
-
作者：Xie, Jun; Wang, Qianni; Li, Jiayang; Nie, Yu (Marco)
作者单位：Southwest Jiaotong University; Northwestern University; University of Hong Kong
摘要：The continuous bi-criteria traffic assignment (C-BiTA) problem aims to find the distribution of agents with heterogeneous preferences in a network. The agents can be seen as playing a congestion game, and their payoff is a linear combination of time and toll accumulated over the selected path. We rediscover a formulation that enables the development of a novel and highly efficient algorithm. The novelty of the algorithm lies in a decomposition scheme and a special potential function. Together,...
-
作者：Jasin, Stefanus; Liu, Sheng; Zhao, Jinglong
作者单位：University of Michigan System; University of Michigan; University of Toronto; Boston University
摘要：We study the inventory allocation problem for an online retailer with multiple warehouses and geographically dispersed demand. The retailer fulfills customer orders using a greedy policy (i.e., ship from the cheapest available warehouse) and determines inventory allocation using the widely adopted hindsight or stochastic programming approach. Although this approach is popular in both academia and practice, its limitations remain poorly understood. We show that the hindsight solution coincides ...
-
作者：Correa, Jose; Cristi, Andres; Dutting, Paul; Hajiaghayi, Mohammad; Olkowski, Jan; Schewiore, Kevin
作者单位：Universidad de Chile; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Alphabet Inc.; Google Incorporated; University System of Maryland; University of Maryland College Park; University of Cologne; University of Southern Denmark
摘要：In this work, we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting, the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already, or it can decide to sell and collect the current price as a reward if it holds the item. We identify settings in which a constant-factor buy-a...
-
作者：Angelopoulos, Spyros; Lidbetter, Thomas; Panagiotou, Konstantinos
作者单位：Centre National de la Recherche Scientifique (CNRS); Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; University of Munich
摘要：We introduce the study of search games between a mobile Searcher and an immobile Hider in a new setting in which the Searcher has some potentially erroneous information, or prediction, on the Hider's position. The objective is to establish tight tradeoffs between the consistency of a search strategy (i.e., its worst-case expected payoff assuming the prediction is correct) and its robustness (i.e., the worst-case expected payoff without any assumptions on the quality of the prediction). Our stu...
-
作者：You, Zhengzhong; Yang, Yu; Wang, Xinshang; Yin, Wotao
作者单位：State University System of Florida; University of Florida; State University System of Florida; University of Florida
摘要：Branching is one of the most important components in branch-price-and-cut (BPC) algorithms for solving vehicle routing problems (VRPs) exactly. However, learning to branch is much more challenging in BPC than in branch-and-cut algorithms that are used for solving general mixed integer programs because branching, in this case, is generally performed by adding a dense constraint to the restricted master problem (RMP), and meanwhile, the variables in the RMP change constantly. To address such cha...
-
作者：Chen, Zhuoxin; Ma, Will
作者单位：Tsinghua University; Columbia University; Columbia University
摘要：In the newsvendor problem, the goal is to guess the number that will be drawn from some distribution, with asymmetric consequences for guessing too high versus too low. In the data-driven version, the distribution is unknown, and one must work with samples from the distribution. The data-driven newsvendor problem has been studied under many variants: additive versus multiplicative regret, high-probability versus expectation bounds, and different distribution classes. This paper studies all com...
