-
作者：Gupta, Varun
作者单位：University of Chicago
摘要：In this paper, we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem when the corresponding static planning linear program (SPP) exhibits a nondegeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward-maximizing SPP is the same as a feasibility linear program restricted to the optimal basic activities, and under GPG, this solution can be tracked with bounded re...
-
作者：Schulz, Andreas S.; Telha, Claudio
作者单位：Technical University of Munich; Technical University of Munich; Universidad de los Andes - Chile
摘要：Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint repleni...
-
作者：Nannicini, Giacomo
作者单位：International Business Machines (IBM); IBM USA
摘要：We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. We show how to quantize all steps of the simplex algorithm, including checking optimality, unboundedness, and identifying a pivot (i.e., pricing the columns and performing the ratio test) according to Dantzig's rule or the steepest edge rule. The quantized subroutines obtain a polynomial speedup in the dimension of the problem but have worse dependence on other numerical parameters. For...
-
作者：Yan, Xiaoyue; Chen, Li; Ding, Xiaobo
作者单位：University of Oregon; Cornell University
摘要：Payables finance, also known as reverse factoring or supply chain finance, is a form of trade finance arrangement that provides a supplier with the option to receive a buyer's payables early while allowing the buyer to extend its payment due date. The recent adoption of the blockchain technology has the potential to make payables finance more efficient and secure. In this paper, we study the supplier's optimal cash policy under such a frictionless payables finance arrangement. Our work extends...
-
作者：Keskin, N. Bora; Li, Meng
作者单位：Duke University; University of Houston System; University of Houston
摘要：. In this paper, we study a firm's dynamic pricing problem in the presence of unknown and time-varying heterogeneity in customers' preferences for quality. The firm offers a standard product as well as a premium product to deal with this heterogeneity. First, we consider a benchmark case in which the transition structure of customer heteroge-neity is known. In this case, we analyze the firm's optimal pricing policy and characterize its key structural properties. Thereafter, we investigate the ...
-
作者：Freund, Daniel; Lykouris, Thodoris; Weng, Wentao
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We study decentralized multiagent learning in bipartite queueing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, that is, by running the same algorithm without communication. Previous decentralized algorithms are restricted to symmetric systems, have performance that is degrading exponentially in the number of servers, require communication through shared randomness and unique agent identities, and are computat...
-
作者：Wang, Jie; Gao, Rui; Zha, Hongyuan
作者单位：The Chinese University of Hong Kong, Shenzhen; University of Texas System; University of Texas Austin; The Chinese University of Hong Kong, Shenzhen; Shenzhen Institute of Artificial Intelligence & Robotics for Society
摘要：In a sequential decision-making problem, off-policy evaluation estimates the expected cumulative reward of a target policy using logged trajectory data generated from different behavior policy, without execution of the target policy. Reinforcement learning in high-stake environments, such as healthcare and education, is often limited to off-policy settings due to safety or ethical concerns or inability of exploration. Hence, it is imperative to quantify the uncertainty of the off-policy estima...
-
作者：Kamble, Vijay; Loiseau, Patrick; Walrand, Jean
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Max Planck Society; University of California System; University of California Berkeley
摘要：We describe an approximate dynamic programming (ADP) approach to compute approximations of the optimal strategies and of the minimal losses that can be guaranteed in discounted repeated games with vector-valued losses. Among other applications, such vector-valued games prominently arise in the analysis of worst-case regret in repeated decision making in unknown environments, also known as the adversarial online learning framework. At the core of our approach is a characterization of the lower ...
-
作者：Qu, Zihao; Dawande, Milind; Janakiraman, Ganesh
作者单位：University of Texas System; University of Texas Dallas
摘要：Motivated by the rapid growth of the cloud cost management and optimization (CCMO) industry to support the exploding cloud-computing market, we study an infinite horizon, stochastic optimization problem from the viewpoint of a firm that employs cloud resources to process incoming orders (or jobs) over time. We model the following vital practical features of CCMO in our problem. There are several types of resources that differ in their costs and performance attributes (e.g., processor speed, me...
-
作者：Jagabathula, Srikanth; Rusmevichientong, Paat; Venkataraman, Ashwin; Zhao, Xinyi
作者单位：New York University; University of Southern California; University of Texas System; University of Texas Dallas
摘要：We describe an efficient estimation method for large-scale tree logit models, using a novel change-of-variables transformation that allows us to express the negative log-likelihood as a strictly convex function in the leaf node parameters and a difference of strictly convex functions in the nonleaf node parameters. Exploiting this representation, we design a fast iterative method that computes a sequence of parameter estimates using simple closed-form updates. Our algorithm relies only on firs...
