Operations Research

最新文章

• Projected Inventory-Level Policies for Lost Sales Inventory Systems: Asymptotic Optimality in Two Regimes AI翻译
  作者：Jaarsveld, Willem van; Arts, Joachim
  作者单位：Eindhoven University of Technology; University of Luxembourg
  摘要：We consider the canonical periodic review lost sales inventory system with positive lead times and stochastic i.i.d. demand under the average cost criterion. We introduce a new policy that places orders such that the expected inventory level at the time of arrival of an order is at a fixed level and call it the projected inventory-level policy. We prove that this policy has a cost rate superior to the equivalent system where excess demand is backordered instead of lost and therefore, is asympt...
• Single-Product Assemble-to-Order Systems with Exogenous Lead Times AI翻译
  作者：Muharremoglu, Alp; Yang, Nan; Geng, Xin
  作者单位：Amazon.com; University of Miami
  摘要：We study a single -product assemble -to -order (ATO) system with exogenous lead times operated under a component base stock policy. Both demand and component lead times are random and are assumed to have finite supports. The challenge of evaluating a base stock policy in an ATO system with random lead times lies in the fact that one needs to compute the distribution of the minimum of n correlated random variables, where n is the number of components. The correlation arises because the replenis...
• Simple Monotonic Readjustment Policies with Applications to Markdown Pricing and Pricing in the Presence of Strategic Customers AI翻译
  作者：Chen, Yiwei; Jasin, Stefanus
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Temple University; University of Michigan System; University of Michigan
  摘要：We consider a canonical revenue management problem wherein a monopolist seller seeks to maximize expected total revenues from selling a fixed inventory of a product to customers who arrive sequentially over time, and the seller is restricted to implement a pricing policy that is monotonic (either nonincreasing or nondecreasing) over time. Gallego and Van Ryzin [Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8...
• Stochastic Liquidity as a Proxy for Nonlinear Price Impact AI翻译
  作者：Muhle-Karbe, Johannes; Wang, Zexin; Webster, Kevin
  作者单位：Imperial College London
  摘要：Optimal execution and trading algorithms rely on price impact models, such as the propagator model, to quantify trading costs. Empirically, price impact is concave in trade sizes, leading to nonlinear models for which optimization problems are intractable, and even qualitative properties, such as price manipulation, are poorly understood. However, we show that in the diffusion limit of small and frequent orders, the nonlinear model converges to a tractable linear model. In this high-frequency ...
• On Proportionally Consistent Solutions to the Divorced-Parents Problem AI翻译
  作者：Romeijnders, Ward; Van Foreest, Nicky D.; Wijngaard, Jacob
  作者单位：University of Groningen
  摘要：When Dutch parents divorce, Dutch law dictates that the parental contributions to cover the financial needs of the children have to be proportionally consistent. This rule is clear when parents only have common children. However, cases can be considerably more complicated, for example, when parents have financial responsibilities to children from previous marriages. We show that, mathematically, this settlement problem can be modeled as a bipartite rationing problem for which a unique global p...
• Resource-Aware Cost-Sharing Methods for Scheduling Games AI翻译
  作者：Christodoulou, George; Gkatzelis, Vasilis; Sgouritsa, Alkmini
  作者单位：Aristotle University of Thessaloniki; Drexel University; Athens University of Economics & Business
  摘要：We study the performance of cost-sharing methods in a selfish scheduling setting where a group of users schedule their jobs on machines with load-dependent cost functions, aiming to minimize their own cost. Anticipating this user behavior, the system designer chooses a decentralized protocol that defines how the cost generated on each machine is to be shared among its users, and the performance of the protocol is evaluated over the Nash equilibria of the induced game. Previous work on selfish ...
• A Low-Rank Approximation for MDPs via Moment Coupling AI翻译
  作者：Zhang, Amy B. Z.; Gurvich, Itai
  作者单位：Cornell University; Northwestern University
  摘要：We introduce a framework to approximate Markov decision processes (MDPs) that stands on two pillars: (i) state aggregation, as the algorithmic infrastructure, and (ii) central-limit-theorem-type approximations, as the mathematical underpinning of optimality guarantees. The theory is grounded in recent work by Braverman et al. (2020) that relates the solution of the Bellman equation to that of a partial differential equation (PDE) where, in the spirit of the central limit theorem, the transitio...
• Black-Box Acceleration of Monotone Convex Program Solvers AI翻译
  作者：London, Palma; Vardi, Shai; Eghbali, Reza; Wierman, Adam
  作者单位：California Institute of Technology; Purdue University System; Purdue University; University of California System; University of California Berkeley
  摘要：This paper presents a black-box framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for high-dimensional problems, for which the number of variables n is much larger than the number of measurements m. Given an (m x n) problem, we construct a smaller (m x epsilon n) problem, whose solution we use to find an approximation to the optimal sol...
• Fair and Efficient Online Allocations AI翻译
  作者：Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Alexandros; Zeng, David
  作者单位：Boston University; State University System of Florida; University of Florida; Harvard University; Purdue University System; Purdue University
  摘要：We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. ...
• A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation AI翻译
  作者：Chen, Zaiwei; Maguluri, Siva T.; Shakkottai, Sanjay; Shanmugam, Karthikeyan
  作者单位：University System of Georgia; Georgia Institute of Technology; University of Texas System; University of Texas Austin
  摘要：This paper develops a unified Lyapunov framework for finite-sample analysis of a Markovian stochastic approximation (SA) algorithm under a contraction operator with respect to an arbitrary norm. The main novelty lies in the construction of a valid Lyapunov function called the generalized Moreau envelope. The smoothness and an approximation property of the generalized Moreau envelope enable us to derive a one-step Lyapunov drift inequality, which is the key to establishing the finite-sample bou...