k-服务器及相关问题的在线算法研究

Online algorithm is one of hot research topics in theoretical computer science and combinatorial optimization. In the past several years, the primal-dual method has been successfully applied to the designing of online algorithms for a variety of online problems, such as online covering and packing problems. However, it has not yet penetrated into other fields where online algorithms are of significant interest. We think that there are plenty of other results just below the surface, waiting to be uncovered.The k-server problem is one of the most central and well studied problems in competitive analysis and is considered by many to be the "holy grail" problem in the field. At present, is there an O(log k)-competitive randomized algorithm and a k-competitive deterministic algorithm for the k-server problem in an arbitrary metric space-are important open problems in this field. In this project, we make our efforts to apply the primal-dual method to the designing of online algorithms for the k-sever problem and its related problems. We will study how to design the suitable linear programming formulation for some problems which are related to the k-sever problemthe and how to design more efficient online algorithms from the linear programming formulation and the primal-dual approach, completely or partly solving the k-sever problem.

在线算法的研究是理论计算机科学和组合优化领域中的热门课题之一。近几年来原始-对偶方法成功地应用于一些问题的在线算法设计中，如在线覆盖与填装问题等。然而，它还没有被探索怎样用于其他更多领域的在线算法设计中，我们认为还有大量未知的结果需要去发现。k-服务器问题是在线计算领域中十分重要的和广泛地被研究的问题之一，被许多研究者称为"圣杯"问题。目前，对于k-服务器问题，是否存在竞争比为O(log k)的在线随机算法和竞争比为k的在线确定性算法，这是在线算法领域中的重要的未解决问题。本项目研究用原始-对偶方法设计k-服务器及相关问题的在线算法。我们将研究如何设计与k-服务器相关问题的合适的线性规划表述，以及如何从线性规划表述和原始-对偶方法的技巧设计更有效的在线算法对这些问题，从而设计出k-服务器问题的在线算法，解决或部分解决k-服务器问题。

原始‐对偶方法最初是为了解决线性规划问题而开发出来的，后来成为组合优化的近似算法设计中的一种强大的方法。如何把原始‐对偶方法用于在线算法的设计和分析中?这是近几年来理论计算机科学中非常新的研究方向之一。理论计算机科学家在这方面有一些初步的研究。. 在本项目中，我们探索了利用原始‐对偶方法在k-服务器及相关计算问题的在线算法设计中的应用。还探索了线性规划技术在密集子图相关问题的算法设计中的应用。另外，我们还在一些相关的方向上的问题作出了一些研究如最小整数解问题的近似难解性以及其在签名算法中的应用的研究,组合拍卖问题的近似算法和难解性的研究等等。. 重要的结果有：对于某些限制条件下的度量空间,已经设计出一个随机O(log k)竞争比的随机k-服务器算法。对于分层树的具有k+1个点的度量空间,已经设计出一个O(log k log n)竞争比的随机k-服务器算法。对于集合多覆盖和多槽广告字分配问题，用原始-对偶方法设计了在线算法。证明了大小约束的最小割问题是NP-完全的,设计了多项式时间算法对于最密集子图问题在约束大小为常数大小情况下。设计了近似算法对于特定子集的最密集子图问题。 证明了无穷范式下具有预处理的最小整数解问题是难以逼近, 设计了一个基于格的在标准模型下是安全的线性同态签名算法。