论文标题
基于数量的网络收入管理的近乎最佳的原始二元算法
Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management
论文作者
论文摘要
我们研究了基于规范数量的网络收入管理（NRM）问题，在这些问题中，决策者必须不可撤销地接受或拒绝每个到达的客户请求，以最大程度地利用有限的资源来最大化总收入。由于众所周知的维度诅咒，通过动态编程来解决问题的确切解决方案在计算上是棘手的。文献中的现有作品利用确定性线性程序（DLP）的解决方案来设计渐近最佳算法。这些算法依靠反复求解DLP来实现近乎最佳的遗憾界限。但是，实时反复计算DLP解决方案是耗时的，尤其是在可能涉及数亿个需求单元的大规模问题中。在本文中，我们提出了针对NRM问题的创新算法，该算法易于实施，并且不需要求解任何DLP。我们的算法达到了$ O（\ log K）$的遗憾，其中$ k $是系统尺寸。据我们所知，这是第一个NRM算法（i）具有$ O（\ sqrt {k}）$渐近遗憾的绑定，并且（ii）不需要求解任何DLP。
We study the canonical quantity-based network revenue management (NRM) problem where the decision-maker must irrevocably accept or reject each arriving customer request with the goal of maximizing the total revenue given limited resources. The exact solution to the problem by dynamic programming is computationally intractable due to the well-known curse of dimensionality. Existing works in the literature make use of the solution to the deterministic linear program (DLP) to design asymptotically optimal algorithms. Those algorithms rely on repeatedly solving DLPs to achieve near-optimal regret bounds. It is, however, time-consuming to repeatedly compute the DLP solutions in real time, especially in large-scale problems that may involve hundreds of millions of demand units. In this paper, we propose innovative algorithms for the NRM problem that are easy to implement and do not require solving any DLPs. Our algorithm achieves a regret bound of $O(\log k)$, where $k$ is the system size. To the best of our knowledge, this is the first NRM algorithm that (i) has an $o(\sqrt{k})$ asymptotic regret bound, and (ii) does not require solving any DLPs.
