Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа

• Date: 2013
• Main Author: Mikhailyuk, V. О.
• Format: Article
• Language: Ukrainian
• Published: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013
• Online Access: http://journal.iasa.kpi.ua/article/view/57494
• Journal Title: System research and information technologies

With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a result of minor local modifications of the initial instance. This approach, called reoptimization, allows, for example, in some cases, getting the best quality of approximation (which is defined as the ratio between the value of an approximate solution to the exact ratio and called approximation ratio) in locally modified instances than at initials. If for some tasks approximation ratio can not be improved (e.g. in class of all approximation algorithms with polynomial complexity), the ratio is called the threshold or optimal (algorithm which achieved this ratio is also called the threshold or optimal). The complexity of the algorithms is estimated by the number of hits (queries) to a special oracle. For reoptimization of minimum vertex cover problem (with addition of one vertex and some set of edges) (3/2)-approximation algorithm with additive error and sublinear (constant) complexity is received. It is shown that the approximation ratio of 3/2 is the threshold in the class of algorithms with constant complexity.