互联网通信中的信息选取与分布问题的建模与求解

讨论了互联网通信中的一个信息选取与规划问题。由于内部网的单个Web服务器容量不够大，不能容纳与日剧增的信息内容，如何将众多的信息分布到多个Web服务器上，使得每个服务器上存放的信息总量不超过各个服务器容量且避免访问瓶颈的发生；这是陈卫东等1999年提出的一个新问题，该文建立了该问题的一个优化新模型，在讨论了它的强NP－完全性，难近似性后，给出了一个伪多项式时间最优算法的一个多项式时间近似算法。

The Modeling and Algorithms of Information Organization and Allocation Problem on Internet Communications

With the frequent information accesses from users to the Internet, it is important to organize and allocate the information resources properly on different Web severs. This paper considers the following problem: Due to the capacity limitation of each single Web server, it is impossible to put all information resources on one Web server. Hence it is an important problem to put them on several different servers such that (1) the amount of information resources assigned on any server is not larger than its capacity; (2) the access bottleneck can be avoided. This new open problem was proposed in \ where the simplified version was studied. In order to solve the problem, this paper first introduces an objective function and thus models it as an integer linear programming problem. Then the author analyzes its NP hardness in several cases. A pseudo polynomial time optimal algorithm is presented. Based on the computational complexity results, the paper further focuses on the design of heuristic. To get near optimal solution, the paper presents an approximation algorithm Greedy which runs in O(n log n ) time and has a worst case ratio of 1/2. Moreover, the paper proves that there does not exist a polynomial time approximation algorithm with a worst case ratio better than 7/9. The paper closes with some numerical experiments and conclusions.