-
作者：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...
-
作者：Huang, Chengpiao; Wang, Kaizheng
作者单位：Columbia University; Columbia University
摘要：We develop a versatile framework for statistical learning in nonstationary environments. In each time period, our approach applies a stability principle to select a look-back window that maximizes the utilization of historical data while keeping the cumulative bias within an acceptable range relative to the stochastic error. Our theory showcases the adaptivity of this approach to unknown nonstationarity. We prove regret bounds that are minimax optimal up to logarithmic factors when the populat...
-
作者：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...
-
作者：Arlotto, Alessandro; Keskin, Irem Nur; Wei, Yehua
作者单位：Duke University
摘要：We study a joint inventory placement and online fulfillment model. In the beginning, the inventory is distributed to different warehouses. At each subsequent period, an order arrives from one of the demand regions, and the decision maker makes an irrevocable decision: whether to accept or reject the order and, if accepted, from which warehouse to fulfill it. To study this problem, we introduce the notion of joint (placement and fulfillment) regret, the regret of a given inventory placement and...
-
作者：Lin, Yifan; Wang, Yuhao; Zhou, Enlu
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact permissions@informs.org. The Publisher does not warrant or guarantee the article's accuracy, completeness, merchantability, fitness inclusion of an advertisement in this article, neither constitutes nor implies a guaran...
-
作者：Aid, Rene; Basei, Matteo; Ferrarid, Giorgio
作者单位：Universite PSL; Universite Paris-Dauphine; Institut Polytechnique de Paris; ENSTA Paris; University of Bielefeld
摘要：We consider a mean-field model of firms competing a` la Cournot on a commodity market, where the commodity price is given in terms of a power inverse demand function of the industry-aggregate production. Investment is irreversible and production capacity depreciates at a constant rate. Production is subject to Gaussian productivity shocks, whereas large nonanticipated macroeconomic events driven by a two-state continuous-time Markov chain can change the volatility of the shocks, as well as the...
-
作者：Spiers, Sandy; Bui, Hoa T.; Loxton, Ryan
摘要：The Euclidean max-sum diversity problem becomes substantially more difficult as the number of coordinates increases despite the number of decision variables not changing. In this paper, we overcome this complexity by constructing a new set of locations whose squared Euclidean distances equal that of the original. Using squared distances allows the objective function to be decomposed into the sum of pairwise distances within each coordinate. A partition set of the coordinates is then used to en...
-
作者：He, Taotao; Zhang, Yating; Zheng, Huan
作者单位：Shanghai Jiao Tong University
摘要：This paper examines how to plan multiperiod assortments when customer utility depends on historical assortments. We formulate this problem as a nonlinear integer programming model and show it is NP-hard in the presence of a negative historydependent effect (such as a satiation effect). We build solution methodologies for obtaining global optimal solutions under a general setting where the history-dependent effects could be a mixture of positive and negative. We propose using a lifting-based fr...
