占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.

Structural lower bound analysis for online vertex covering problem

In the actual process of locating facility,the decision-maker always faces the following constraints :they must determine where to locate the initial facility(or facilities)when the number of edges to be served is uncertain,and,the constructed facilities can not be removed when the new facility is built. The existed models and algorithms are always pointed to a static facility location process,but here we need a dynamic facility location model with above constraints.Considered the online vertex covering problem in this paper,we present a structural lower bound which does not need any complexity assumption,and prove that the analysis is tight by giving a competitive algorithm as well as competitive ratio proof for a restricted version of the online vertex covering problem,and we also obtain that this algorithm is optimal if we are permitted to use non-polynomial time.