Operations Research

最新文章

• Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization AI翻译
  作者：Guo, Siqi; Xiao, Fan; Liang, Zhe
  作者单位：Tongji University; Shanghai University
  摘要：It is widely acknowledged that deep dual-optimal inequalities (DDOIs) can stabilize the dual of a linear programming problem and accelerate its convergence. However, we find that adding DDOIs is not free but always comes with a price; that is, it increases the number of primal degenerate bases, and extra effort might be needed to achieve dual feasibility and prove its optimality. As a result, when addressing a linear programming problem, it is critical to stabilize the dual on the one hand, re...
• Optimal Abort Policy for Mission-Critical Systems Under Imperfect Condition Monitoring AI翻译
  作者：Sun, Qiuzhuang; Hu, Tiawen; Ye, Zhi-Sheng
  作者单位：University of Sydney; University of Electronic Science & Technology of China; National University of Singapore
  摘要：Although most on-demand mission-critical systems are engineered to be reliable to support critical tasks, occasional failures may still occur during missions. To increase system survivability, a common practice is to abort the mission before an imminent failure. We consider optimal mission abort for a system whose deterioration follows a general three-state (normal, defective, failed) semi-Markov chain. The failure is assumed selfrevealed, whereas the healthy and defective states have to be in...
• Event-Triggered Bayesian Control Chart AI翻译
  作者：Abbou, Abderrahmane; Makis, Viliam
  作者单位：Mohammed VI Polytechnic University; University of Toronto
  摘要：This paper develops the Bayesian analogue to the Shewhart type control chart previously developed for systems monitored by online sensors. Unlike previous work, we allow production sampling to be part of the decision process, so that a decision to take a sample is first made when a sensor generates a warning signal, followed immediately by another decision to interrupt operation. We apply optimal stopping theory along with dynamic programming analysis to prove the average cost optimality of a ...
• Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources AI翻译
  作者：Goyal, Vineet; Iyengar, Garud; Udwani, Rajan
  作者单位：Columbia University; University of California System; University of California Berkeley
  摘要：We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources for which an adversarial sequence of resource requests is revealed over time and any allocated resource is used/rented for a stochastic duration drawn independently from a resource-dependent usage distribution. Previously, it was known that a greedy algorithm is 0.5-competitive against the clairvoyant benchmark that knows the entire sequence of requests in advance. We give a nov...
• On Multivariate Singular Spectrum Analysis: Tensor and Matrix Variants AI翻译
  作者：Agarwal, Anish; Alomar, Abdullah; Shah, Devavrat
  作者单位：Columbia University; Massachusetts Institute of Technology (MIT)
  摘要：We introduce and analyze two extensions of singular spectrum analysis (SSA) to the multivariate setting: a new variant of the well-known matrix-based method (mSSA) and a novel tensor-based approach (tSSA). Under a spatio-temporal factor model, we establish prediction-error guarantees for mSSA for both imputation and out-of-sample forecasting. By exploiting both spatial and temporal structure, mSSA achieves better rates than univariate SSA and standard matrix estimation methods. The out-of-samp...
• Sinkhorn Distributionally Robust Optimization AI翻译
  作者：Wang, Jie; Gao, Rui; Xie, Yao
  作者单位：The Chinese University of Hong Kong, Shenzhen; University of Texas System; University of Texas Austin; University System of Georgia; Georgia Institute of Technology
  摘要：We study distributionally robust optimization with Sinkhorn distance: a variant of Wasserstein distance based on entropic regularization. We derive a convex programming dual reformulation for general nominal distributions, transport costs, and loss functions. To solve the dual reformulation, we develop a stochastic mirror descent algorithm with biased subgradient estimators and derive its computational complexity guarantees. Finally, we provide numerical examples using synthetic and real data ...
• Deterministic Budget-Feasible Clock Auctions AI翻译
  作者：Balkanski, Eric; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel; Tan, Xizhi
  作者单位：Columbia University; Drexel University; Rutgers University System; Rutgers University New Brunswick
  摘要：We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategy-proof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer while eliciting each seller's true cost for providing their service. Our main result in this paper is a novel method for designing budget-feasible auctions, lead...
• Long-History Principal Component Analysis in a Dynamic Factor Model with Weak Loadings AI翻译
  作者：Anderson, Robert M.; Kim, Baeho; Ryu, Dean
  作者单位：Harbin Institute of Technology; University of California System; University of California Berkeley; Korea University; Instituto Tecnologico Autonomo de Mexico
  摘要：Estimated covariance and precision matrices of asset returns significantly influence the set of portfolios compliant with risk budgets and their potential losses. Statistical risk modeling approaches often assume temporal stability for consistency with a static factor structure, typically estimated within TM-250 days of data history, resulting in finitesample estimation error when the dimension of the population exceeds the number of observations. Our study investigates the application of Prin...
• The Pre-hedging AI翻译
  作者：Muhle-Karbe, Johannes; Oomen, Roel
  作者单位：Imperial College London; Deutsche Bank
  摘要：This paper studies a dealer that pre-hedges an anticipated potential trade, and we analyze how this affects the client's overall execution outcome. We show that prehedging can benefit both parties: Improved risk management over an extended horizon enables the dealer to charge reduced spreads that more than offset any adverse impact the pre-hedging activity has on the execution price. However, when a dealer pre-hedges too aggressively, this can be detrimental to the client. Timing uncertainty o...
• Convergence and Inference of Stream Stochastic Gradient Descent, with Applications to Queueing Systems and Inventory Control AI翻译
  作者：Li, Xiang; Liang, Jiadong; Chen, Xinyun; Zhang, Zhihua
  作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen
  摘要：Stream stochastic gradient descent (SGD) is a simple and efficient method for solving online optimization problems in operations research (OR), where data are generated by parameter-dependent Markov chains. Unlike traditional approaches which require increasing batch sizes during iterations, stream SGD uses a single sample per iteration, significantly improving sample efficiency. This paper establishes a systematic framework for analyzing stream SGD, leveraging the Poisson equation solution to...