Mathematics of Operations Research

最新文章

• Convex Duality with Transaction Costs AI翻译
  作者：Dolinsky, Yan; Soner, H. Mete
  作者单位：Hebrew University of Jerusalem; Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Finance Institute (SFI)
  摘要：Convex duality for two different super-replication problems in a continuous time financial market with proportional transaction cost is proved. In this market, static hedging in a finite number of options, in addition to usual dynamic hedging with the underlying stock, are allowed. The first one of the problems considered is the model-independent hedging that requires the super-replication to hold for every continuous path. In the second one the market model is given through a probability meas...
• On the Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spaces AI翻译
  作者：Saldi, Naci; Yuksel, Serdar; Linder, Tamas
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Queens University - Canada
  摘要：Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more res...
• Calculating Principal Eigen-Functions of Non-Negative Integral Kernels: Particle Approximations and Applications AI翻译
  作者：Whiteley, Nick; Kantas, Nikolas
  作者单位：University of Bristol; Imperial College London
  摘要：Often in applications such as rare events estimation or optimal control it is required that one calculates the principal eigenfunction and eigenvalue of a nonnegative integral kernel. Except in the finite-dimensional case, usually neither the principal eigenfunction nor the eigenvalue can be computed exactly. In this paper, we develop numerical approximations for these quantities. We show how a generic interacting particle algorithm can be used to deliver numerical approximations of the eigenq...
• Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints AI翻译
  作者：Gayon, Jean-Philippe; Massonnet, Guillaume; Rapine, Christophe; Stauffer, Gautier
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; IMT Atlantique; Universite de Lorraine
  摘要：We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm for this NP-hard problem, by recombining the solutions of single-echelon relaxations at the warehouse and at the retailers. We then show that our approach remains valid under quite general assumptions on the cost structures and under capacity constraints at some retailers. In partic...
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions AI翻译
  作者：Davis, Damek; Yin, Wotao
  作者单位：Cornell University; University of California System; University of California Los Angeles
  摘要：In this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions including strong convexity, Lipschitz differentiability, and bounded linear regularity. The main consequence of this work is that relaxed PRS and ADMM automatically adapt to the regularity of the problem and achieve convergence rates that improve upon...
• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems AI翻译
  作者：Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
  作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan; Carnegie Mellon University
  摘要：We consider the problem of constructing optimal decision trees: given a collection of tests that can disambiguate between a set of m possible diseases, each test having a cost, and the a priori likelihood of any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? This problem has been studied in several works, with O(log m)-approximations known in the special cases when either costs or probabilities are uniform. In ...
• A Sublogarithmic Approximation for Tollbooth Pricing on Trees AI翻译
  作者：Gamzu, Iftah; Segev, Danny
  作者单位：Yahoo! Inc; Yahoo! Inc Israel; University of Haifa
  摘要：An instance of the tollbooth problem consists of an undirected network and a collection of single-minded customers, each of which is interested in purchasing a fixed path subject to an individual budget constraint. The objective is to assign a per-unit price to each edge in a way that maximizes the collective revenue obtained from all customers. The revenue generated by any customer is equal to the overall price of the edges in her desired path, when this cost falls within her budget; otherwis...
• Characterizations of Smooth Ambiguity Based on Continuous and Discrete Data AI翻译
  作者：Minardi, Stefania; Savochkin, Andrei
  作者单位：Hautes Etudes Commerciales (HEC) Paris; New Economic School
  摘要：In the Anscombe-Aumann setup, we provide conditions for a collection of observations to be consistent with a well-known class of smooth ambiguity preferences (Klibanoff P, Marinacci M, Mukerji S (2005) A smooth model of decision making under ambiguity. Econometrica 73(6): 1849-1892.). Each observation is assumed to take the form of an equivalence between an uncertain act and a certain outcome. We provide three results that describe these conditions for data sets of different cardinality. Our f...
• On the Width of Semialgebraic Proofs and Algorithms AI翻译
  作者：Razborov, Alexander
  作者单位：University of Chicago; University of Chicago; Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences
  摘要：In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvatal cutting planes and Lovasz-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimi...
• The Power of Slightly More than One Sample in Randomized Load Balancing AI翻译
  作者：Ying, Lei; Srikant, R.; Kang, Xiaohan
  作者单位：Arizona State University; Arizona State University-Tempe; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：In many computing and networking applications, arriving tasks have to be routed to one of many servers, with the goal of minimizing queueing delays. When the number of processors is very large, a popular routing algorithm works as follows: select two servers at random and route an arriving task to the least loaded of the two. It is well known that this algorithm dramatically reduces queueing delays compared to an algorithm, which routes to a single randomly selected server. In recent cloud com...