Sublinear optimal approximate algorithm of reoptimization for minimum vertex cover problem
Abstract
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.References
Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning and approximation // Journal of the ACM. — 1998. — 45(4). — P. 653–750.
Goldreich O., Ron D. Property testing in bounded degree graphs // Algorithmica. — 1997. — 32(2). — P. 302–343.
Bogdanov A., Obata Kenji, Trevisan L. A lower bound for testing 3-colorability in bounded-degree graphs // In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science. — 2002. — P. 93–102.
Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the traveling salesman problem // Networks. — 2003. — 42 (3). — P. 154–159.
Mikhaylyuk V.А., Sergiyenko I.V. Reoptimizatsiya obobshchennykh problem o vypolnimosti s approksimatsionno-ustoychivymi predikatami // Kibernetika i sistemyy analiz. — 2012. — 48, № 1. — S. 89–104.
Marko S., Ron D. Distance approximation in bounded-degree and general sparse graphs // In Proceedings of the Tenth International Workshop on Randomization and Computation (APPROX-RANDOM). Lecture Notes in Computer Science. — 2006. — 4110. — P. 475–486
Parnas M., Ron D. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms // Theoretical Computer Science. — 2007. — 381(1–3). — P.183–196.
Hastad J. Some optimal inapproximability results // Journal of the ACM. — 2001. — 48, № 4. — P. 798–859.
Khot S., KIndler G., Mossel E., O’Donnell R. Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? // In FOCS. — 2004. — P.146–154.
Khot S. On the Unique Games Conjecture // In Proc. of the 25-th Annual IEEE Conference on Computational Complexity. — 2010. — P. 99–121.
