1期

最新文章

• A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing AI翻译
  作者：Engineer, Faramroze G.; Furman, Kevin C.; Nemhauser, George L.; Savelsbergh, Martin W. P.; Song, Jin-Hwa
  作者单位：University of Newcastle; Exxon Mobil Corporation; University System of Georgia; Georgia Institute of Technology
  摘要：A branch-price-and-cut algorithm is developed for a complex maritime inventory-routing problem with varying storage capacities and production/consumption rates at facilities. The resulting mixed-integer pricing problem is solved exactly and efficiently using a dynamic program that exploits certain extremal characteristics of the pricing problem. The formulation is tightened by using the problem's boundary conditions in preprocessing and to restrict the set of columns that are produced by the p...
• Approximation Algorithms for VRP with Stochastic Demands AI翻译
  作者：Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
  作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA; Carnegie Mellon University
  摘要：We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + alpha for split-delivery VRPSD, and 2 + alpha for unsplit-delivery VRPSD; here alpha is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error ...
• A Copulas-Based Approach to Modeling Dependence in Decision Trees AI翻译
  作者：Wang, Tianyang; Dyer, James S.
  作者单位：Colorado State University System; Colorado State University Fort Collins; University of Texas System; University of Texas Austin
  摘要：This paper presents a general framework based on copulas for modeling dependent multivariate uncertainties through the use of a decision tree. The proposed dependent decision tree model allows multiple dependent uncertainties with arbitrary marginal distributions to be represented in a decision tree with a sequence of conditional probability distributions. This general framework could be naturally applied in decision analysis and real options valuations, as well as in more general applications...
• Asymptotic Optimality of Balanced Routing AI翻译
  作者：Chen, Hong; Ye, Heng-Qing
  作者单位：Shanghai Jiao Tong University; Hong Kong Polytechnic University
  摘要：Consider a system with K parallel servers, each with its own waiting room. Upon arrival, a job is routed to the queue of one of the servers. Finding a routing policy that minimizes the total workload in the system is a known difficult problem in general. Even if the optimal policy is identified, the policy would require the full queue length information at the arrival of each job; for example, the join-the-shortest-queue policy (which is known to be optimal for identical servers with exponenti...
• On the Complexity of Nonoverlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems AI翻译
  作者：Doan, Xuan Vinh; Natarajan, Karthik
  作者单位：University of Warwick; University of Warwick; City University of Hong Kong
  摘要：Given a combinatorial optimization problem with an arbitrary partition of the set of random objective coefficients, we evaluate the tightest-possible bound on the expected optimal value for joint distributions consistent with the given multivariate marginals of the subsets in the partition. For univariate marginals, this bound was first proposed by Meilijson and Nadas [Meilijson, I., A. Nadas. 1979. Convex majorization with an application to the length of critical path. J. Appl. Probab. 16(3) ...
• Price of Correlations in Stochastic Optimization AI翻译
  作者：Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu
  作者单位：Stanford University; Stanford University
  摘要：When decisions are made in the presence of high-dimensional stochastic data, handling joint distribution of correlated random variables can present a formidable task, both in terms of sampling and estimation as well as algorithmic complexity. A common heuristic is to estimate only marginal distributions and substitute joint distribution by independent (product) distribution. In this paper, we study possible loss incurred on ignoring correlations through a distributionally robust stochastic pro...
• Pricing Asian Options Under a Hyper-Exponential Jump Diffusion Model AI翻译
  作者：Cai, Ning; Kou, Steven
  作者单位：Hong Kong University of Science & Technology; Columbia University
  摘要：We obtain a closed-form solution for the double-Laplace transform of Asian options under the hyper-exponential jump diffusion model. Similar results were available previously only in the special case of the Black-Scholes model (BSM). Even in the case of the BSM, our approach is simpler as we essentially use only Ito's formula and do not need more advanced results such as those of Bessel processes and Lamperti's representation. As a by-product we also show that a well-known recursion relating t...
• Sequential Correlated Equilibria in Stopping Games AI翻译
  作者：Heller, Yuval
  作者单位：University of Oxford; University of Oxford
  摘要：In many situations, such as trade in stock exchanges, agents have many opportunities to act within a short interval of time. The agents in such situations can often coordinate their actions in advance, but coordination during the game consumes too much time. An equilibrium in such situations has to be sequential in order to handle mistakes made by players. In this paper, we present a new solution concept for infinite-horizon dynamic games, which is appropriate for such situations: a sequential...