论文标题
单程交易和在线背包问题的最佳在线算法问题：统一竞争分析
Optimal Online Algorithms for One-Way Trading and Online Knapsack Problems: A Unified Competitive Analysis
论文作者
论文摘要
我们在容量/预算限制下研究两个规范的在线优化问题：分数单向交易问题（OTP）和在无限假设下的整体在线背包问题（OKP）。在竞争性分析框架下，众所周知，这两个问题具有相同的最佳竞争比率。但是，这两个问题是通过文献中不同背景下的不同方法研究的。了解这两个问题与其在线算法设计的性质之间的联系存在差距。本文为这两个问题的在线算法设计，分析和最佳证明提供了一个统一的框架。我们发现，OKP的无限假设是连接OTP在线算法和最坏情况实例的构建中连接OTP的键。有了这种统一的理解，我们的框架显示了以更系统的方式分析OKP和OTP的其他扩展的潜力。
We study two canonical online optimization problems under capacity/budget constraints: the fractional one-way trading problem (OTP) and the integral online knapsack problem (OKP) under an infinitesimal assumption. Under the competitive analysis framework, it is well-known that both problems have the same optimal competitive ratio. However, these two problems are investigated by distinct approaches under separate contexts in the literature. There is a gap in understanding the connection between these two problems and the nature of their online algorithm design. This paper provides a unified framework for the online algorithm design, analysis and optimality proof for both problems. We find that the infinitesimal assumption of the OKP is the key that connects the OTP in the analysis of online algorithms and the construction of worst-case instances. With this unified understanding, our framework shows its potential for analyzing other extensions of OKP and OTP in a more systematic manner.
