Mathematics of Operations Research

最新文章

• The Linear Complementarity Problems with a Few Variables per Constraint AI翻译
  作者：Sumita, Hanna; Kakimura, Naonori; Makino, Kazuhisa
  作者单位：University of Tokyo; University of Tokyo; Kyoto University
  摘要：In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i. e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known...
• On Error Estimates for Asymptotic Expansions with Malliavin Weights: Application to Stochastic Volatility Model AI翻译
  作者：Takahashi, Akihiko; Yamada, Toshihiro
  作者单位：University of Tokyo
  摘要：This paper proposes a unified method for precise estimates of the error bounds in asymptotic expansions of an option price and its Greeks (sensitivities) under a stochastic volatility model. More generally, we also derive an error estimate for an asymptotic expansion around a general partially elliptic diffusion and a more general Wiener functional, which is applicable to various important valuation and risk management tasks in the financial business such as the ones for multidimensional diffu...
• Equimeasurable Rearrangements with Capacities AI翻译
  作者：Ghossoub, Mario
  作者单位：Imperial College London
  摘要：In the classical theory of monotone equimeasurable rearrangements of functions, equimeasurability (i.e., that two functions have the same distribution) is defined relative to a given additive probability measure. These rearrangement tools have been successfully used in many problems in economic theory dealing with uncertainty where the monotonicity of a solution is desired. However, in all of these problems, uncertainty refers to the classical Bayesian understanding of the term, where the idea...
• Tight Approximations of Dynamic Risk Measures AI翻译
  作者：Iancu, Dan A.; Petrik, Marek; Subramanian, Dharmashankar
  作者单位：Stanford University; International Business Machines (IBM); IBM USA
  摘要：This paper compares two frameworks for measuring risk in a multiperiod setting. The first corresponds to applying a single coherent risk measure to the cumulative future costs, and the second involves applying a composition of one-step coherent risk mappings. We characterize several necessary and sufficient conditions under which one measurement always dominates the other and introduce a metric to quantify how close the two measures are. Using this notion, we address the question of how tightl...
• Optimal Information Blending with Measurements in the L2 Sphere AI翻译
  作者：Defourny, Boris; Ryzhov, Ilya O.; Powell, Warren B.
  作者单位：Lehigh University; University System of Maryland; University of Maryland College Park; Princeton University
  摘要：A sequential information collection problem, where a risk-averse decision maker updates a Bayesian belief about the unknown objective function of a linear program, is used to investigate the informational value of measurements performed to refine a robust optimization model. The information is collected in the form of a linear combination of the objective coefficients, subject to random noise. We have the ability to choose the weights in the linear combination, creating a new, nonconvex contin...
• Fluid Limits of G/G/1+G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline AI翻译
  作者：Atar, Rami; Biswas, Anup; Kaspi, Haya
  作者单位：Technion Israel Institute of Technology; Technion Israel Institute of Technology
  摘要：A single-server queueing model is considered with customers that have deadlines. If a customer's deadline elapses before service is offered, the customer abandons the system (customers do not abandon while being served). When the server becomes available, it offers service to the customer having the earliest deadline among those that are in the queue. We obtain a fluid limit of the queue length and abandonment processes and for the occupation measure of deadlines, in the form of measure-valued...
• On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs AI翻译
  作者：Girardeau, P.; Leclere, V.; Philpott, A. B.
  作者单位：Institut Polytechnique de Paris; Ecole des Ponts ParisTech; University of Auckland
  摘要：We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of stochastic dual dynamic programming, cutting-plane and partial-sampling (CUPPS) algorithm, and dynamic outer-approximation sampling algorithms when applied to problems with...
• Parameter Estimation: The Proper Way to Use Bayesian Posterior Processes with Brownian Noise AI翻译
  作者：Cohen, Asaf
  作者单位：Technion Israel Institute of Technology
  摘要：This paper studies a problem of Bayesian parameter estimation for a sequence of scaled counting processes whose weak limit is a Brownian motion with an unknown drift. The main result of the paper is that the limit of the posterior distribution processes is, in general, not equal to the posterior distribution process of the mentioned Brownian motion with the unknown drift. Instead, it is equal to the posterior distribution process associated with a Brownian motion with the same unknown drift an...
• Facility Location with Matroid or Knapsack Constraints AI翻译
  作者：Krishnaswamy, Ravishankar; Kumar, Amit; Nagarajan, Viswanath; Sabharwal, Yogish; Saha, Barna
  作者单位：Princeton University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan; International Business Machines (IBM); IBM India; AT&T
  摘要：In the classical k-median problem, we are given a metric space and want to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper we present the first constant-factor approximation algorithms for two natural generalizations of this problem that handle matroid or knapsack constraints. In the matroid median problem, there is an underlying matroid on the vertices and the set of open centers is constrained to be ind...
• Approximation Algorithm for the Stochastic Multiperiod Inventory Problem via a Look-Ahead Optimization Approach AI翻译
  作者：Truong, Van-Anh
  作者单位：Columbia University
  摘要：We consider the single-item, multiperiod stochastic inventory problem with nonstationary and correlated demands. We provide the first proof that a well-known myopic policy, which we call look-ahead optimization (LA), is in fact an approximation algorithm for solving the large dynamic program that arises from this problem. We prove that LA provides the tightest known approximation bound for this problem. The expected cost of LA is at most twice the expected holding cost plus the expected backor...