Structural lower bound analysis for online vertex covering problem
Wenqiang Dai · Systems Engineering - Theory & Practice · 2012
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.