Article citationsMore>>

S. Khot, G. Klendler, E. Mossel and R. O’Donnell, “Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?” Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Rome, 17-19 October 2004, pp. 146-154. doi:10.1109/FOCS.2004.49

has been cited by the following article:

• TITLE: Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems

  AUTHORS: Victor Alex Mikhailyuk

  KEYWORDS: C-Approximation Algorithm; Reoptimization; Approximation Resistant Predicates; Integrality Gap; Unique Games Conjecture (UGC)

  JOURNAL NAME: American Journal of Operations Research, Vol.3 No.2, March 28, 2013

  ABSTRACT: The purpose of reoptimization using approximation methods—application of knowledge about the solution of the initial instance I, provided to achieve a better quality of approximation (approximation ratio) of an algorithm for determining optimal or close to it solutions of some “minor” changes of instance I. To solve the problem Ins-Max-EkCSP-P (reoptimization of Max-EkCSP-P with the addition of one constraint) with approximation resistant predicate P exists a polynomial threshold (optimal) -approximation algorithm, where the threshold “random” approximation ratio of P). When the unique games conjecture (UGC) is hold there exists a polynomial threshold (optimal) -approximation algorithm (where and the integrality gap of semidefinite relaxation of Max-EkCSP-P problem Z) to solve the problem Ins-Max-EkCSP-P.