CAJ | 학술논문

在实际顶点覆盖选址过程中，经常会遇到如下的情形：在需要服务的边的个数未知的前提下，决策者需要决定在哪里建立初始的设施（或设施集），同时还要求，当新的设施建立后，前面已经建立的设施不能被删除．以往一般建立的模型和算法都是针对静态选址而言的，这里需要的是满足上述约束的动态选址模型．考虑了占线顶点覆盖问题，给出了一个不需要任何复杂性假设条件下的结构性的下界结果，并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的，同时证明了所给出的算法在非多项式时间内是最优的．
재실제정점복개선지과정중，경상회우도여하적정형：재수요복무적변적개수미지적전제하，결책자수요결정재나리건립초시적설시（혹설시집），동시환요구，당신적설시건립후，전면이경건립적설시불능피산제．이왕일반건립적모형화산법도시침대정태선지이언적，저리수요적시만족상술약속적동태선지모형．고필료점선정점복개문제，급출료일개불수요임하복잡성가설조건하적결구성적하계결과，병통과대일개한제성조건하적점선정점복개문제급출산법병증명경쟁성능비결과설명료소작적하계분석시긴적，동시증명료소급출적산법재비다항식시간내시최우적．
In the actual process of locating facility, the decision-maker always faces the tbllowing con- straints： 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.