Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems

American Journal of Operations Research, 2013, 3, 279-288 doi:10.4236/ajor.2013.32025 Published Online March 2013 (http://www.scirp.org/journal/ajor) Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems Victor Alex Mikhailyuk V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine Email: [email protected] Received November 23, 2012; revised December 25, 2012; accepted January 8, 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 (reopti- nomial threshold (optimal)   q  P   -approximation algorithm, where   q  P    2   2  d  P   2  2 k P 1 1 mization of Max-EkCSP-P with the addition of one constraint) with approximation resistant predicate P exists a poly- q P  1 ( d  P  - the threshold “random” approximation ratio of P). When the unique games conjecture (UGC) is hold there ex- ists a polynomial threshold (optimal)   Z  -approximation algorithm (where   Z   2  and  Z - the inte- Z 1 grality gap of semidefinite relaxation of Max-EkCSP-P problem Z) to solve the problem Ins-Max-EkCSP-P. Keywords: C-Approximation Algorithm; Reoptimization; Approximation Resistant Predicates; Integrality Gap; Unique Games Conjecture (UGC)  OPT 1  C  , where 1. Introduction 1 tive function value no less than In the constraint satisfaction problems (or CSP problems), C there are many variables and a set of constraints (defined OPT—the global optimum. In this C is called the ap- by predicates), each of which depends on a number of proximation ratio. Such a definition can be given to variables, and the goal is to find such assigning values to minimization problems. variables that satisfy the maximum number of constraints. For the problem Q an upper bound of approximation predicates over a finite domain  q   1, 2, , q . Each More formally, CSP problem Q is defined by a set of ratio is established, if there exists a polynomial C-ap- proximation algorithm for solving Q. For the problem Q for any   0 there is no polynomial approximation the lower bound of approximation ratio c is established, if instance of problem Q consists of a set of variables V and algorithm for Q where the approximation ratio c   (or a set of constraints on it. The goal is to find the assignment to variables that satisfies the maximum number of con- strictly less than c) is achieved. If C = c, then, for the straints. In general, the predicates can be replaced with problem Q the threshold of approximation ratio is estab- actual payoff functions, and the goal is to maximize the lished (is equal to C = c). The corresponding algorithm is total payment. A large number of fundamental optimiza- called the threshold or optimal (and the approximation tion problems, such as Max Cut and Max k-Sat, there are ratio-optimal). examples of CSP problems. A fundamental question for a given NP-hard problem is Most of the CSP problems are NP-hard and so to solve to determine for which values you can rely on efficient them exactly in a reasonable time is hardly possible. (polynomial) C-approximation algorithm. This is a large Therefore we considered an effective approximation al- research area in theoretical computer science with its gorithm for solving such problems. For the maximization positive and negative results. problem saying that the algorithm is the C-approximation The problem of establishing lower bounds for the ap- algorithm, if for any instance gives a solution with objec- proximation ratio (like any problem of obtaining lower Copyright © 2013 SciRes. AJOR 280 V. A. MIKHAILYUK bounds for the complexity) is a very difficult task. For this The question arises: how can we effectively utilize the of exact or approximate solution of the instance I  ? The problem there is the name of inapproximability or the knowledge of the optimal solution of I for the calculation hardness of approximation. Great influence on the de- velopment of methods for obtaining lower bounds the purpose of reoptimization using approximation methods - famous PCP theorem [1] and discrete Fourier analysis to application of knowledge about the solution of the initial test the properties of problems (property testing) are pro- instance I, provided either to achieve a better quality of vided [2,3]. approximation (approximation ratio), or a more efficient Beginning with Goemans and Williamson [4,5] for (in time) algorithm for determining optimal or close to it Max Cut, semidefinite programming (SDP) has become solutions, or execution of the first and second points. the main tool in the construction of approximation algo- Such results for the reoptimization of discrete optimi- rithms for the CSP problems. For many of the problems zation problems are known. When an elementary dis- are built SDP relaxations and apply appropriate proce- junction is inserted reoptimization of Max Weighted Sat dures for the probabilistic rounding the solutions were (weighted satisfiability problem for maximum) approxi- obtained. mated with the ratio of 0.81, while Max Weighted Sat - As already noted, the problem of inapproximability has approximable with ratio 0.77 [25]. When inserting a ver- been solved successfully for many of the problems due to tex in the graph reoptimization of Min Vertex Cover PCP theorem. In particular, Hastad [6-8] showed that (minimum vertex cover of a graph) can be approximated with ratios 2   and 8 7   respectively. This means Max-E3-Lin-2 and Max 3-Sat are NP-hard to approximate with the ratio of 1.5, Min Vertex Cover-with the ratio of 2 [25]. When inserting a vertex (terminal or not) reopti- (optimal) for these problems, if P  NP or that ratios 2 that a simple random algorithm for assigning is the best mization of Min Steiner Tree (minimum Steiner tree) can approximated by the ratio 1  ln  3 2  1.55 [21].When be approximated with the ratio of 1.5, Min Steiner Tree- and 8/7 are the threshold. In [9] is showed (also involving PCP theorem) that the set covering problem has a thresh-  1  you insert or delete an item from a set, the set covering problem is approximable with ratio  2   , where old approximation ratio equal to ln n . In studying the problem of inapproximability for gen-  ln m 1  eral constraints satisfaction problems (in particular with m—the number of elements. A similar result occurs the predicates of arity 2), such progress was not achieved. 1  p  m elements of the set [26]. It should be noted a when you insert or delete an arbitrary number of The most promising approach to obtaining strong results (thresholds of approximation ratios)—the so called Unique series of papers on the problem of reoptimization of trav- Games Conjecture (UGC), introduced by S. Khot [11-14]. eling salesman problem (TSP-Travelling Salesman Unique games conjecture (UGC) is one of the most im- Problem) [20-22,24]. For example, the problem of Min- portant open problems in modern theoretical computer imum Metric TSP (Min TSP—the traveling salesman science because of the large number of strong results in problem with the minimum metric distances) approxi- ple, 2   —the hardness of approximating Vertex Cover inapproximability that follow from the UGC. For exam- mable with ratio 1.5, its reoptimization when inserting a new unit—with ratio of 1.34, reoptimization of this prob- [12], Max Independent Set [15], Multi Cut [16]. Recently, a close relationship between the concepts of lem when you change the distance—with ratio of 1.4 the approximation ratio, the inapproximability ratio and [25]. For the general traveling salesman problem (Min integrality gap of simple SDP relaxation (defined as the TSP) are unknown estimates of approximation ratio as maximum ratio of the SDP solution to the real optimum) for herself, and for different versions of reoptimization. has been established. From the truth of UGC, it follows The main results of this paper are as follows. We in- that the simple SDP relaxation gives the optimal ap- vestigated the reoptimization versions of constraint sat- proximation ratio for CSP. For the first time link between isfaction problems with predicates of arity k (Ins-Max- the SDP rounding schemes for relaxation and results in EkCSP-P) by adding of any constraint. To solve the problem Ins-Max-EkCSP-P (reoptimization Max-EkCSP- polynomial threshold (optimal)   q  P   —approxima- innapproximability based on the UGC, was noticed in [13] for Boolean CSP of two variables. In general, in [17-19] P) with approximation resistant predicates there exists a proposed the rounding schemes by which the optimal tion algorithm, where   q  P   2  approximation ratio for each CSP problem, assuming the  2  d  P   2  2 k P 1 1 q  P true UGC, is achieved. 1 The concept of reoptimization [20-26] is as follows. Let ( d  P  —the threshold “random” approximation ratio). Q-some NP-hard (perhaps NP-complete) problem, I-the which is known. We propose a new instance I  of the initial problem instance of Q, the optimal solution of exists a polynomial threshold (optimal)   Z  —appro- When the unique games conjecture (UGC) is hold there problem Q, received some “minor” changes of instance I. Copyright © 2013 SciRes. AJOR  V. A. MIKHAILYUK 281 ximation algorithm (where   Z   2  and  Z — Z 1 constant, is the problem Max-k-LIN. If each constraint contains exactly k literals, that is the problem Max-Ek- Let wopt  I  is the value of the optimal solution of in- the integrality gap of semidefinite relaxation of Max- LIN. EkCSP-P problem Z) to solve the problem Ins-Max- EkCSP-P. stance I . Definition 5. The algorithm A is C-approximation al- of the problem w  A, I    wopt  I  , where w  A, I  - 2. Preliminaries gorithm for the maximization problem if for all instances I 1 Present the necessary notations and definitions [6,28,31]. C P : 1,1  0,1 . For notational convenience, the Under the predicate P of arity k we mean the map the value of the solution of algorithm A for the input I. In k abilistic algorithms w  A, I  - the expected value of ran- this talk, that A has the approximation ratio C. For prob- input data with a value of −1 is interpreted as “true”, value then P  y   1 , else P  y   0 . Thus, the set of values of 1-as “false”. If the predicate P accepts an input value y accepted by the predicate P, is denoted as P 1 1 . Logic dom elections of algorithm A. The predicate P is approximation resistant (and the corresponding problem Max-CSP-P), if to find a solution x  y, x  y and x  y , respectively. For integer k de- AND, OR and XOR with two variables is denoted as Max-CSP-P, that is much better than expected value of random assignment, is NP-hard. Because of random as- d  P   2 k P 1 1 , we have the following definition. note predicates kOR, kAND and kXOR as a logical OR, kXOR  x1 , , xk   1 , then  x1 , , xk  has odd parity, signment accept any P-constraint with probability Definition 6. The predicate P : 1,1  0,1 is AND and XOR of the k variables, respectively. If k called approximation resistant if for any constant   0 else even parity. Literal—a Boolean variable or its nega- tion.  d  P   P : 1,1  0,1 . An instance of the problem Max- to find a solution x of instance I of the problem Max- Definition 1. Suppose there is a predicate CSP-P such, that the value x no more than wopt  I  , is NP -hard. k   1  1 CSP-P consists of m weighted constraints, each of them  x1 , , xn , x1 , , xn  . All variables in the tuple are dif- is a k-tuple of literals zi1 , , zik drawn from the set proximable, if for any   0 there exists    0 and an Definition 7. The problem Max-CSP-P is always ap-  d  P   ferent. Constraint is satisfied if and only if P accepts a  x1 , , xn  . Value of the solution is  wi P  zi , , zi , tuple. The solution is the assignment of truth values to efficient algorithm, which is based on an instance, where 1  m 1 some -part of constraints may be si-  d  P   i 1 1 k multaneously accepted, find the assignment, that accept 1   1 where wi is (not negative) weight of i-th constraint. The Definition 8. The predicate P : 1,1  0,1 is goal is to maximize this value. When P depends on no no more than -part of the constraints. more than k literal Max-CSP-P will be called Max- k kCSP-P, if in P exactly k literals-then Max-EkCSP-P. cates P  which are consequences of P (i.e. called hereditary approximation resistant if all the predi-  P  y   1   P  y   1 , for all y) are approximation Along with the problems of the type Max-CSP-P dis- cussed problems such as CSP-P, where the goal is to find such assignment, that all constraints are satisfied (kCSP-P resistant. Definition 2. Two k-arity predicates P and P  have and EkCSP-P similarly defined). Theorem 1 [8]. The problem Max-CSP-P admits a on  k   1, , k and a  1,1 , such that  d  P  the same type if and only if there exists a permutation π polynomial approximation algorithm with approximation   1 P  x1 , , xk   P  a1 xπ 1 , , ak xπ  k  for all x  1,1 . k ratio . k Proof. Let us have an instance with m constraints. If P and P  have the same type, then an instance probability d  P  and, thus, accepted d  P   m con- Random assignment accepted any given constraint with a Max-CSP-P can be expressed as an instance Max-CSP-P', straints on average. Since the optimal assignment ac-  d  P   - approximation algorithm. That random algo- rearranging the tuples according to the mask, i.e., these cepted no more than m constraints, we have the random 1 problems are equivalent. Definition 3. Problem Max-kCSP-P, where each con- straint is disjunction of no more than k literals is a problem rithm may be derandomized dy the method of conditional Max-k-SAT. If each constraint contains exactly k literals, expectation. that is the problem Max-Ek-SAT. Remark 1. For approximation resistant predicates P Definition 4. Problem Max-kCSP-P, where each con- threshold approximation ratio of the problem Max-CSP-P straint is a product of no more than k literals equal to a is attained (Theorem 1) and equals Copyright © 2013 SciRes. AJOR 282 V. A. MIKHAILYUK 1  q  P    d  P    2k P 1 1  1 .   P  P :  q    1,1 t  k , a lot of payoff functions. t P   is the dimension of the problem  . This value is called the threshold “random” approxi- The maximum number of inputs of the payoff function Definition 10. An instance  of the problem Λ-GCSP mation ratio. is defined as   V , V , W  , where We have the following results on approximation resis- predicate of arity 2  k  2  , which are approximation  V   y1 , , ym  : variables taking values from  q  ; tant predicates of Max-EkCSP-P problems. There is no resistant [8]. If k  3 the problem Max-E3-LIN is he-  V consists of the payoff functions that are applied to precisely, for a subset S  s1 , s2 , , st   1, , m reditary approximation resistant [6], and it exhausts all of subsets S of variables V of size no more than k. More proximation resistant predicates of arity 4  k  4  are t payoff function PS  V is applied to the variables   approximation resistant predicates of arity 3 [29]. Ap- yS  ys1 , , yst ;  positive weights W  wS  satisfy  S V , S k wS  1 , studied in [28]. There are 400 different predicates (up to S  W denote the set S, chosen according to prob- permutations of variables and their negations). Among them, 79 were identified as approximation resistant, 275- not as approximation resistant, the status of the remaining ability distribution W. 46 predicates could not be determined. The goal is to find the assignment of variables that maximize E  PS  yS     wS P  y S  (denote this Present the main results for approximation resistant maximize the expected total weight or total weight, i.e. Theorem 2 [6]. For an arbitrary   0 it is NP -hard S  m, S  k SW predicates of arity 3 (Max-E3CSP-P). to approximate Max-E3-LIN with ratio 2   . In other maximum as opt    ). Theorem 3 [6]. For an arbitrary   0 it is NP -hard the problem Λ-GCSP is unweighted  wS  1 , then words Max-E 3-LIN is approximation resistant. Note, that if the payoff functions P are predicates, and opt    will be just the maximum number of accepted to approximate Max-E3-LIN with ratio   . In other 8 We introduce the predicate XOR  x1 , x2   x1  x2 . In constraints. 7 words Max-E3-LIN is approximation resistant. P  x, y, z   1 for any x, y, z, satisfying the equation xyz = the future, as an example, we consider the problem Max Theorem 4 [6]. Let P the predicate of arity 3 such, that Cut. G  V , E  with set vertices V and edges E of Max Cut is Definition 11 (Max Cut). For a given undirected graph the problem of finding a partition C  V1 , V2  of the 1, then CSP, determined by P, is approximation resistant. vertices V V  V1  V2 , V1  V2    , that maximizes the Theorem 4 remains true if we replace the equation xyz = 1 by xyz = −1. Generalization of Theorem 4 is the fol- size of the set V1  V2   E . For a given weight function lowing theorem. w : E  R  , weighted Max Cut problem is to maximize Theorem 5 [8]. Predicate P of arity 3 is approximation  w e . resistant, if and only if it is a consequence of the odd eV1 V2   E parity or even parity. XOR  x1 , x2 , x3   x1  x2  x3 Consider the following predicates of arity 3: For a graph G  V , E  with set vertices V and edges E Let us consider in more detail the problem Max Cut. NTW  x1 x2 , x3    x1  x2  x3   x1  x2  x3 this problem (the maximum cut in the graph) is defined as OXR  x1 , x2 , x3   x1   x2  x3  follows: find a partition V on V1 and V2 to maximize the OR  x1 , x2 , x3   x1  x2  x3 . number of edges, that form a cut, i.e. lies between the two xi  xi  1, i  V1 , xi  1, i  V2  , then the problem can be parts. If each vertex i associate a Boolean variable The above results can be summarized in the following equations of the form xi x j  1 . viewed as Max-E2CSP-XOR or Max-E2-LIN with the assertion. Theorem 6. Predicates XOR, NTW, OXR, OR are ap- proximation resistant predicates. Among them XOR, 3. On Computational Complexity of NTW, OXR-hereditary approximation resistant predi- Reoptimization cates. Z (Definition 1). Let V   x1 , , xn , x1 , , xn  the set of Following [30,31] we introduce a generalization of the Consider an arbitrary unweighted Max-EkCSP-P problem cates with values from 0,1 , payoff functions with variables, E-the set of constraints. The constraint e  E   CSP problem (GCSP problems), where instead of predi- values from  1,1 to be used. is denoted as e  xe1 , , xek , ei   2  n  with a special defined as    q  , , k  where  q   0,1, , q  1 , map  : V  0,1 , the assignment  accepted con- Definition 9 (Λ-GCSP problem). Λ-GCSP problem is order of the variables (relative to V). The assignment is a Copyright © 2013 SciRes. AJOR  283      V. A. MIKHAILYUK straint e, if P  xe1 , ,  xek  1 . We denote by OPT  I  the maximum part of the constraints accepted how to do it for Max-Ek-Lin. Theorem 7. The problem Ins-Max-Ek-Lin is NP-hard.   by any assigning an arbitrary instance I of the problem Z. Proof. We use Lemma 1. As P we take a NP-hard E  e  , e  , , e  - the set of m constraints. The con- Let an instance I of the problem Z such, that problem Max-Ek-Lin [8], but as a mod-P-problem Ins- 1 2 m Max-Ek-Lin. Let I—an arbitrary instance of the problem straint e   E is denoted as e    x  j  , , x  j   , equations). Let xi1  xi2    xik  b -one of these Max-Ek-Lin (it corresponds to a system L of m linear  e1 ek  j j ei   2  n  , 1  j  m, 1  i  k  with a special order of  j equations (we take it as I  ). Construct in polynomial time the variables (relative to V). An instance I  of the prob- an assignment of values to vector x   x1 , , xn  , which lem is obtained from I by adding an arbitrary  m  1 -th    x1 , , xn  arbitrary values of truth. If xi1 , xi2 , , xik makes this equation acceptable. We assign the set of constraint e m1 (the same structure, as e  ,1  j  m ). satisfies equation I  then the build is completed, other- j wise any value xil  l   k  is reversed, resulting in the Define reoptimization version of the problem Max- equation I  will be accepted in polynomial time, i.e. EkCSP-P. point 1) and 2) of Lemma 1 are satisfied. As I  can be Problem Ins-Max-EkCSP-P. Input. Arbitrary instance I of the problem Max-EkCSP-P, x —the optimal solu- transformed into I no more than m modifications mod-P Result. Find the optimal solution of instance I  (ob- tion of instance I. (i.e., add no more than m equations), point 3) of Lemma 1 tained on the basis of I, as described above) of the problem is also fulfilled and the theorem is proved. Max-EkCSP-P, using x . 4. Reoptimization of Constraint Satisfaction cepted constraints of instance I  . Purpose. Find x, that maximizes the number of ac- Problems with Approximation Resistant Theorem 8. If k  O  log n  and for the problem Max- Useful and interesting are challenges to establishing of Predicates NP -hardness of reoptimization versions of optimization problems. Using the results of [27] (in particular Theorem EkCSP-P exists a polynomial  -approximation algo- mization Max-EkCSP-P) exists a polynomial     — 2), we propose a criterion for determining of NP-hardness rithm, then for the problem Ins-Max-EkCSP-P (reopti- of reoptimization. The essence of the criterion for the approximation algorithm, where      2  . most of NP-hard problems is that in order to show NP-  1 hardness of reoptimization versions suggestions are based on polynomial Turing reducibility of the original problem   Proof. We apply the approach discussed in [25,26]. Let sists of a system of constraints E  e  , i   m  and to its reoptimization version.   I—an instance of the problem Max-EkCSP-P, which con- Lemma 1. Let P-NP-hard problem and mod-P-some i local modification to P. If there exists a polynomial algo-   optimal solution x , w x - the number of accepted con- straints in the system E by solution x . Adds a constraint rithm A, which for any instance I of the problem P com- e  to the system, the result is an instance I  of the m 1 1) instance I  for mod -P ; putes: problem Max-EkCSP-P, let xI —the best solution of it. If 2) the optimal solution x for I  ; xI does not accepted constraint e  , then x is the m 1 optimal solution of instance I  of the problem Ins-Max- more than a polynomial), that transforms I  into I, then 3) a sequence of local modifications of the type mod (no     E2CSP-P, then w x  w xI  1 the problem mod-P is NP-hard. Proof. Reduce P to mod-P using a polynomial Turing (1) reducibility. Because of P is NP-hard, and that such (i.e., (on the left side write down the condition, that x - the NP-hard) will be mod-P. not accepted constraint e  ). Suppose xI is accepted best solution, and the right, that the optimal solution does m 1 mod for A that I  is converted into an instance I. Sup- Let q—the number of local modifications of the type  m 1 constraint is satisfied (obviously, l  2k ). the constraint e and there are l ways in which the We construct l approximate solutions xi  i  l  as pose that there exists a polynomial algorithm A1 (with since with I  , we find the optimal solution for I. At the complexity p) for mod-P. Then, using A1 exactly q times follows. Take i-th assignment, which accepted e  . same time as the number of calculations  q  and time of m 1  m 1 each calculation  p  , polynomial in the size of P, we From the constraint system we remove e and for the ment) use a polynomial  - approximation algorithm, we constraints, that remain (including the result of assign- q  p ). Lemma is proved. obtained polynomial reducibility (with the complexity    w  x   1  1  w  x   1  obtain an approximate solution xi . The result is from NP-hardness of Max-EkCSP-P (at k  2 ) set NP- Using Lemma 1, it is possible for specific predicates P w xi       1 1 1 I I (2) hardness of Ins-Max-EkCSP-P. For example, we show Copyright © 2013 SciRes. AJOR 284 V. A. MIKHAILYUK nomial-time algorithm with approximation ratio   , less Multiplying (1) on 1  than  , that is impossible).  1 and adding with (2) we ob- polynomial threshold (optimal)  -approximation algo- Theorem 10. If for a problem Max-EkCSP-P exists a     tain  1 1   w x  w x  rithm and k  O  log n  , then for the problem Ins-Max-   i polynomial threshold (optimal)     -approximation     EkCSP-P (reoptimization Max-EkCSP-P), there exists a  1  1 1   1   w xI   1    w xI  1        algorithm, where      2  . 1    1  w xI Corollary 1. If k  O  log n  and the predicate P ap- The proof follows from Theorems 8 and 9 Among the solutions x and xi choose the best (i.e., with the largest value of the objective function w) and is proximation resistant, then for the problem Ins-Max- a polynomial optimal r  P  -approximation algorithm, EkCSP-P (reoptimization of Max-EkCSP-P), there exists      denoted by x . We have    1  w xI   1   1 max w x , w xi where r  P   2k 1  P 1 1    .  1   2   w x , 2k  Proof. Since the predicate P is approximation resistant,   Max-EkCSP-P is optimal q  P  -approximation algo- according to Remark 1, the algorithm of Theorem 1 for and w  x     rithm, where q  P    d  P   , d  P   2 k P 1 1 . 1 w xI . To the algorithm is polyno- 2 1  1 mial was sufficient to require that 2k  nc (n-the total a polynomial threshold (optimal)   q  P   -approxima- Hence, by Theorem 10 for Ins-Max-EkCSP-P there exists k  O  log n  in the theorem. Thus, as a result of this tion algorithm, where   q  P   2  number of variables, c = const), which means algorithm, an approximate solution x of the instance I   2  d  P   2  2 k P 1 1 . q  P 1 with approximation ratio      2   1 is obtained. It is Example 1. Consider the problem Max-E3CSP-XOR clear that at all times 2       1 . with the appropriate reoptimization version Ins-Max-  1 E3CSP-XOR. By Theorem 6, the predicate XOR- is he-   reditary approximation resistant (there is proof of this fact polynomial threshold (optimal)  -approximation algo- ollary 1) k  3, P 1 1  4 and obtain proposition. Theorem 9. If for a problem Max-EkCSP-P exists a in [28]). We apply Theorem 10 (or more precisely, Cor- zation Max-EkCSP-P), there exists a polynomial  -ap- rithm, and for the problem Ins-Max-EkCSP-P (reoptimi- Proposition 1. For the problem Ins-Max-E3CSP-XOR proximation algorithm, then       . (reoptimization of Max-E3CSP-XOR) there exists a   polynomial optimal approximation algorithm with an ap- which consists of a system of constraints E  e  , i  m  Proof. Let I- an instance of the problem Max-EkCSP-P, 3 i proximation ratio . 2   m 1 system, the result is an instance I  of the problem Ins- and optimal solution x . Adds a constraint e to the 5. Integrality Gaps of Semidefinite Relaxation For each instance   V , V , W  (Definition 10) is Max-EkCSP-P. Let x - the solution of Ins-Max-EkCSP-   P, obtained by the algorithm of Theorem 6. The solution of the solutions x , and xi i  l  , l  2k , it is obtained not presented here). Let sdp    -solution of SDP re- x is the best (more on the value of the objective function) constructed semidefinite (SDP) relaxation [30] (which is laxation (clearly, sdp     opt    ). We introduce the by a polynomial approximation algorithm with approxi- mation ratio      2  . The proof is by contradic-  1 tion. Let       and   - such, that        . notion of integrality gap for semidefinite relaxation of the constraint satisfaction problems. Since the function     is increasing in  and  sdp                 , it follows, that     . But this Definition 12. Integrality gap ofΛ-GCSP problem is defined as    sup     opt       exists a polynomial threshold (optimal)  -approxima- contradicts the fact, that for the problem Max-EkCSP-P The notion of integrality gap for some relaxation (not tion algorithm (i.e., for solutions xi to be applied poly- only semidefinite) is important, because it allows to de- Copyright © 2013 SciRes. AJOR  V. A. MIKHAILYUK 285 sign approximation algorithms for solving discrete opti- where  GW  0.878567 a known Goemans-Williamson mization problems with a given approximation ratio. The constant). Thus, the approximation algorithm not only following theorem holds. finds an approximate optimum value, but also gives an Theorem 11 [31]. For the problem Λ-GCSP with non- approximate cut. This feature is characteristic of most Theorem 13 [10]. For any   0 there exists a graph negative payoff functions there exists a polynomial ap- algorithms based on SDP and LP (linear) relaxation. than integrality gap   . SDP  G  π 1  cos  c proximation algorithm with approximation ratio no more G V , E  such, that     . Thus This theorem can comment on such arguments. First, OPT  G  2 c the problem Λ-GCSP), let  gen the solution of it. Ap-  SDP  G   π 1  cos  c we solve the problem SDPgen (general SDP relaxation of  MC  sup     OPT  G   2 c , combining with lution  gen we obtain an approximate solution  appr of plying some probabilistic scheme of rounding, from so- π 1  cos  c G w   gen      w   appr  (where w   denotes the Theorem 12, we obtain  MC   c the original problem Λ. By Definition 12 we obtain . A lower bound for integrality gap is a graph G V , E  , 2 w   appr    w   gen   weight of the solution), then  opt    where the bound is attained. Corresponding instance of   1 1 the problem is Integrality Gap Instance (IGI). and, by definition 5, we received an   —approximation So, for Max Cut managed to find the exact value of the integrality gap of SDP relaxation. algorithm. Note, that the calculation (estimation) of integrality 6. Unique Games Conjecture and gaps of relaxations is in itself a difficult research task. For Reoptimization many problems it is still unsolvable. However, even Unique Games Conjecture (UGC) was introduced by without knowing the specific values of the integrality gaps Khot [11] as a possible way to obtain new results on of relaxations, one can argue about the existence of strong innapproximability. We formulate the UGC in threshold (optimal) approximation algorithms for opti- terms of Unique Game Problem. mization problems (which will be noted later). Definition 13. A Unique Game Problem is a constraint a directed graph G V , E  , whose vertices represent To illustrate, consider the Max Cut problem. Let vi -a satisfaction problem, which is defined as follows. There is unit vector in Euclidean space, which corresponds to a Boolean variable xi . We have the following SDP re- variables and edges-constraints. The purpose is to as- on the edge e   v, w   E is described by a bijection laxation of Max Cut:  1 1  vi  v j   , i   n  , vi  1 , signing a label to each vertex from the set [n]. Constraint max   π e :  n    n  . Labeling the vertices L : V   n  satis-  E  fies (accepts) a constraint on the edge e   v, w  , iff  i , j E π e  L  v    L  w  . Let OPT U  denote the maximum 2 where vi  v j - the scalar product vi and v j . We define an integrality gap  MC of this relaxation:  SDP  G   part of constraints, which may be satisfied by any label-  MC  sup   , where SDP  G  —the optimum G  OPT  G   ing: OPT U   max   e  E L satisfied e  .    1    of relaxation. L:V  n  E Theorem 12 [5].  π 1  cos    ,   0 there exists a constant n  n   ,   such that, Unique Games Conjecture (UGC) [11]. For any  MC  max          0,π   2 π 1  cos  c U G V , E  ,  n  , π e e  E is NP-hard to distinguish for this instance of unique game problem    1.138, c  YES case: OPT U   1   2 between two cases: where  c is the “critical angle” at which the maximum is  NO case: OPT U    . attained. A typical technique to obtain the results on innap- Goemans and Williamson give random rounding algo- proximability can be described as follows. The source is rithm (now known as the random hyperplane rounding the following argument. Suppose P- an arbitrary optimi- cut in a graph with a value no less, than 1  MC times the  c.s  -gap version of the problem P (notation algorithm) that for any solution of SDP relaxation find a zation (to be specific to a maximum of) problem. Under once expected SDP solution (note that  GW  1  MC , Gap-Pc , s ) we understand the problem, for which either Copyright © 2013 SciRes. AJOR 286 V. A. MIKHAILYUK OPT  I   c , or OPT  I   s for any instance I  P . Using Theorems 11 and 14, we get a result. and any   0 rounding scheme RS determines the ap- Consider the NP-complete problem 3-Sat (3-Satisfi- Corollary 2 [30]. Assuming the UGC for any GCSP proximation ratio in the range  of optimal polynomial ability). Arbitrary 3-Sat formula (E3-CNF formula) is the algorithm, i.e. for any GCSP problem  there exists a conjunction of a set of clauses, where each clause is the polynomial threshold (optimal)   -approximation al- disjunction of three Boolean variables or their negations. The goal is to determine the assignment of a Boolean variable, such that the formula is logically true (accept- gorithm. of 3-Sat to Gap-Pc , s for some 0  s  c , that is, re- lem Z (definition 1). Let V   x1 , , xn , x1 , , xn  the set able). Suppose that there exists a polynomial reducibility Consider an arbitrary unweighted Max-EkCSP-P prob- ducibility, which displays a 3-Sat formula  to an in-   e  E is denoted as e  xe1 , , xek , ei   2  n  with of variables, E—the set of constraints. The constraint (YES case): If  has an assignment, that makes it stance I of the problem P such that: acceptable, then OPT  I   c ; is a map  :V  0,1 , assignment  accepts con-      special order on the variables (relative to V). Assignment (NO case): If  has no assignments, that make it ac- straint e, if. P  xe1 , ,  xek  1 . We denote by ceptable, then OPT  I   s . OPT  I  the maximum part of constraints accepted by an Let SDP  I  denote the optimum SDP relaxation of This reducibility implies that if there exists a polyno- arbitrary assigning for instance I of the problem Z . mial algorithm with approximation ratio strictly less than  SDP  I   c Raghavendra [30], we define an integrality gap  Z  sup  for the problem P, then it is possible to efficiently  . In [31] showed how to round a I Z  OPT  I   s   hence P  NP . Thus, under the standard assumption, determine whether a 3SAT formula is satisfiable, and that P  NP this reducibility—the source of results on solution and find assignment with the approximation ratio close to  Z (theorem 11). Let  Z  , then the result of c inapproximability of the problem P. We start from the PCP (Prababilistically Checkable Proof) Theorem [1] in s one form or another for some NP-complete language (for Raghavendra [30] in this case can be presented as a   theorem. Theorem 15 [14]. Suppose there is an instance I  of example, 3-Sat). We construct a reducibility to the prob- Max-EkCSP-P problem Z such, that SDP I   c and   lem (language), which inapproximability to install (for OPT I   s . Then for any   0 there exist  ,   0 example, Gap-Pc , s ). Constructed PCP verifier for the problem P , which is in the form of a test (dictatorship) to the Boolean function that is responsible to P. Using the and polynomial reducibility from the instance of unique  (YES case): If OPT U   1   , then OPT  I   c   ; elements and some of the results of Fourier analysis of game problem to the instance I of problem Z such, that:  (NO case): If OPT U    , then OPT  I   s   . Boolean functions, estimated completeness c of the veri- fier (the lower bound of the probability of accepting the proximate Z with ratio strictly less than  Z . test, that a Boolean function-dictatorship or YES case) In particular, assuming the UGC, it is NP-hard to ap- and soundness s of verifier (the upper bound of the probability of not accepting the test, that Boolean function Corollary 3. Assuming the UGC, for every Max- (optimal)  Z —approximation algorithm. is far from dictatorship or NO case). It follows that P NP- EkCSP-P problem Z there exists a polynomial threshold hard to approximate with a ratio smaller than c/s. This is a common inapproximability. The proof follows from theorems 11, 14 and 15. If not proceed from the PCP theorem, but from the Note that theorem 15 converts the integrality gap into unique game conjecture (UGC) in the above reducibility, inapproximability gap. Roughly speaking the idea is to we receive inapproximability based on UGC or condi- use integrality gap instance (IGI) of SDP relaxation for the Let sdp    the solution of SDP relaxation of in- tional inapproximability. construction of a dictatorship test and combining it with an instance of unique game problem. The value of the stance  of GCSP problem  . In [30] to get closer to result of Raghavendra is that even without knowing ex- the optimal solution proposed scheme of rounding plicitly the exact value of integrality gap, you can set an (Rounding Scheme, RS). In this paper, studies are being optimality of corresponding polynomial approximation conducted in the language of integrality gap curve and algorithm (using IGI). For example, in [32] showed that an integrality gap coefficient   . We will assume that unique games hardness curve. We describe the result with although for Grothendieck’s Problem integrality gap K G k  const . (the famous Grothendieck’s constant) are still unknown, based on the UGC it is NP-hard to approximate the problem  and any   0 it is NP-hard to approximate Theorem 14 [30]. Assuming the UGC, for any GCSP problem of Grothendieck with an arbitrary ratio less than  with approximation ratio   - . K G can be calculated with some error  in the time K G ( K G -approximation algorithm is optimal). Constant Copyright © 2013 SciRes. AJOR  V. A. MIKHAILYUK 287 dependent only on  . problem U  Gap -U1 ,  is NP-hard problem. Along respect to inclusion (for example, P  NP ? ) it is one of Theorem 16. Suppose that a unique game conjecture with the problems of complexity class relationships with  SDP  I   (UGC) is hold. Let Z is any unweighted Max-EkCSP-P problem with integrality gap  Z  sup   and I Z  OPT  I   the major open problems of modern theoretical computer   science. Even if the UGC is false, you may find that Gap -U1 , is hard in the sense of undecidability in k = const, then for the problem Ins-Max-EkCSP-P (reop- polynomial time, and such (a weak) hardness can be ap- threshold (optimal)   Z  -approximation algorithm, timization of Max-EkCSP-P) there exists a polynomial plied to all problems, where the hardness show up on the where   Z   2  basis of UGC. Z 1 . REFERENCES The proof follows by applying corollary 3 to theorem [1] S. Arora, C. Lund, R. Motwani, M. Sudan and M. 10. Szegedy, “Proof Verification and Intractability of Ap- Example 2. Consider the problem Max Cut. In our proximation Problems,” Journal of the ACM, Vol. 45, No. notation, this is a problem Max-E2CSP-XOR, and reop- 3, 1998, pp. 501-555. doi:10.1145/278298.278306 timization version—the problem Ins-Max-E2CSP-XOR, [2] O. Goldreich, S. Goldwasser and D. Ron, “Property Test- obtained by adding an arbitrary edge to Max Cut. By ing and Its Connection to Learning and Approximation π 1  cos  c theorems 12 and 13 integrality gap of SDP relaxation of Abstract,” Journal of the ACM, Vol. 45, No. 4, 1998, pp. problem Max Cut is  MC    1.138 . Then 653-750. doi:10.1145/285055.285060 2 c [3] O. Goldreich and M. Sudan, “Locally Testable Codes and PCPs of Almost-Linear Length,” Journal of the ACM, from theorem 16 follows proposition 2. Vol. 53, No. 4, 2006, pp. 558-655. Proposition 2. Suppose that a unique games conjecture doi:10.1145/1162349.1162351 (UGC) is hold. Then for the problem Ins-Max-E2CSP- mial threshold (optimal)   MC  -approximation algo- [4] M. X. Goemans and D. P. Williamson, “Improved Ap- XOR (reoptimization of Max Cut) there exists a polyno- proximation Algorithms for Maximum Cut and Satisfi- rithm, where   MC   2  ability Problems Using Semidefinite Programming,”  1.121 .  MC 1 Journal of the ACM, Vol. 42, No. 6, 1995, pp. 1115-1145. doi:10.1145/227683.227684 [5] M. X. Goemans and D. P. Williamson, “0.878 Approxi- mation Algorithms for MAX-CUT and MAX-2SAT,” In: 7. Conclusions Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC), ACM, Montreal, 1994, pp. To solve the problem Ins-Max-EkCSP-P (reoptimization there exists a polynomial threshold (optimal)   q  P   - 422-431. of Max-EkCSP-P) with approximation resistant predicates [6] J. Hastad, “Some Optimal Inapproximability Results,” Journal of the ACM, Vol. 48, No. 4, 2001, pp. 798-859. approximation algorithm, where   q  P   2  doi:10.1145/502090.502098  2  d  P   2  2 k P 1 1 q  P 1 [7] J. Hastad, “Complexity Theory, Proofs and Approxima- tion,” European Congress of Mathematics, Stockholm, ( d  P  —the threshold “random” approximation ratio of 2005. [8] J. Hastad, “On the Efficient Approximability of Constraint P). Note that the property of the approximation resistance Satisfaction Problems,” In: A. Hilton and J. Talbot, Eds., may be stronger than the property of NP-completeness of Surveys in Combinatorics 2007, London Mathematical corresponding decision problem. Since in this case the Society Lecture Notes Series (No. 346), Cambridge Uni- versity Press, Cambridge, 2007, pp. 201-222. effective computation can not gives anything more than a doi:10.1017/CBO9780511666209.008 random assignment of truth values to variables. Using the results of [30,31] it can be argued, that if the [9] U. Feige, “A Threshold of lnn for Approximating Set a polynomial threshold (optimal)   Z  —approximation Cover,” Journal of the ACM, Vol. 45, No. 4, 1998, pp. unique games conjecture (UGC) is hold, then there exists 634-652. doi:10.1145/285055.285059 [10] U. Feige and G. Schechtman, “On the Integrality Ratio of timization of Max-EkCSP-P), where  Z —the integrality algorithm to solve the problem Ins-Max-EkCSP-P (reop- Semidefinite Relaxations of MAX CUT,” In: Proceedings of the 23rd Annual ACM Symposium on Theory of Com- gap of SDP relaxation of Max-EkCSP-P problem. puting, ACM, New York, 2001, pp. 433-442. The results of this work greatly depend on the truth of [11] S. Khot, “On the Power of Unique 2-Prover 1-Round the unique game conjecture (UGC). Note that if U- the Games,” In: Proceedings of the 34th Annual ACM Sym- follows: 1   ,   —gap version of the unique games unique games problem, the UGC can be formulated as posium on Theory of Computing, ACM, New York, 2002, pp. 767-775. Copyright © 2013 SciRes. AJOR 288 V. A. MIKHAILYUK [12] S. Khot and O. Regev, “Vertex Cover Might be Hard to [22] H.-J. Bockenhauer, J. Hromkovic, T. Momke and P. Approximate to within 2 − ε,” Journal of Computer and Widmayer, “On the Hardness of Reoptimization,” In: V. System Sciences, Vol. 74, No. 3, 2008, pp. 335-349. Geffert et al., Eds., SOFSEM, Lecture Notes in Computer doi:10.1016/j.jcss.2007.06.019 Science, Vol. 4910, Springer, Berlin, 2008, pp. 50-65. [13] S. Khot, G. Klendler, E. Mossel and R. O’Donnell, “Op- [23] B. Escoffier, M. Milanic and V. Th. Paschos, “Simple and timal Inapproximability Results for Max-Cut and Other fast Reoptimizations for the Steiner Tree Problem,” Algo- 2-Variable CSPs?” Proceedings of 45th Annual IEEE rithmic Operations Research, Vol. 4, No. 2, 2009, pp. 86- Symposium on Foundations of Computer Science (FOCS), 94. Rome, 17-19 October 2004, pp. 146-154. [24] C. Archetti, L. Bertazzi and M. G. Speranza, “Reopti- doi:10.1109/FOCS.2004.49 mizing the Travelling Salesman Problem,” Networks, Vol. [14] S. Khot, “On the Unique Games Conjecture,” Proceed- 42, No. 3, 2003, pp. 154-159. doi:10.1002/net.10091 ings of the 25th Annual IEEE Conference on Computa- [25] G. Ausiello, V. Bonifacci and B. Escoffier, “Complexity tional Complexity, Cambridge, 9-12 June 2010, pp. 99- and Approximation in Reoptimization,” In: S. B. Cooper 121. and A. Sorbi, Eds., Computability in Context: Computa- [15] A. Samorodnitsky and L. Trevisan, “Gowers Uniformity, tion and Logic in the Real World, Imperial College Press, Influence of Variables, and PCPs,” In: Proceedings of the London, 2011, pp. 101-130. 38th Annual ACM Symposium on Theory of Computing, [26] V. A. Mikhailyuk, “Reoptimization of Set Covering Prob- ACM, New York, 2006, pp. 11-20. lems,” Cybernetics and Systems Analysis, Vol. 46, No. 6, [16] S. Chawla, R. Krauhgamer, R. Kumar, Y. Rabani and D. 2010, pp. 879-883. doi:10.1007/s10559-010-9269-z Sivakumar, “On the hardness of approximating multicut [27] V. A. Mikhailyuk, “General Approach to Estimating the and sparsest-cut,” Proceedings of the 20th Annual IEEE Complexity of Postoptimality Analysis for Discrete Op- Conference on Computational Complexity, San Jose, 11- timization Problems,” Cybernetics and Systems Analysis, 15 June 2005, pp. 144-153. doi:10.1109/CCC.2005.20 Vol. 46, No. 2, 2010, pp. 290-295. [17] P. Austrin, “Balanced Max 2-Sat Might Not be the Hard- doi:10.1007/s10559-010-9206-1 est,” Proceedings of the 39th Annual ACM Symposium on [28] G. Hast, “Beating a Random Assignment,” Doctoral The- Theory of Computing, San Diego, 11-13 June 2007, pp. sis, Royal Institute of Technology, Stockholm, 2005. 189-197. [29] U. Zwick, “Approximation Algorithms for Constraint [18] P. Austrin, “Towards Sharp Inapproximability for Any 2- Satisfaction Problems Involving at Most Three Variables CSP,” In: Proceedings of the 48th Annual IEEE Sympo- per Constraint,” In: Proceedings of the 9th Annual ACM- sium on Foundations of Computer Science, IEEE Com- SIAM Symposium on Discrete Algorithms, Society for puter Society, Washington DC, 2007, pp. 307-317. Industrial and Applied Mathematics, Philadelphia, 1998, [19] M. Lewin, D. Livnat and U. Zwick, “Improved Rounding pp. 551-560. Techniques for the MAX 2-SAT and MAX DI-CUT [30] P. Raghavendra, “Optimal Algorithms and Inapproximabil- Problems,” Proceedings of 9th International Integer Pro- ity Results for Every CSP?” In: Proceedings of the 40th gramming and Combinatorial Optimization Conference Annual ACM Symposium on Theory of Computing, ACM, (IPCO), Lecture Notes in Computer Science, Vol. 2337, New York, 2008, pp. 245-254. Cambridge, 27-29 May 2002, pp. 67-82. doi:10.1007/3-540-47867-1_6 [31] P. Raghavendra and D. Steurer, “How to Round Any CSP?” In: Proceedings of the 50th Annual IEEE Sympo- [20] G. Ausiello, B. Escoffier, J. Monnot and V. Th. Paschos, sium on Foundations of Computer Science, IEEE Com- “Reoptimization of Minimum and Maximum Traveling puter Society, Washington DC, 2009, pp. 586-594. Salesman’s Tours,” Journal of Discrete Algorithms, Vol. 7, No. 4, 2009, pp. 453-463. doi:10.1007/11785293_20 [32] P. Raghavendra and D. Steurer, “Towards Computing the Grothendieck Constant,” Proceedings of the 20th Annual [21] H. J. Bockenhauer, L. Forlizzi, J. Hromkovic, et al., “On ACM-SIAM Symposium on Discrete Algorithms, Society the Approximability of TSP on Local Modifications of for Industrial and Applied Mathematics, Philadelphia, Optimal Solved Instances,” Algorithmic Operations Re- 2009, pp. 525-534. search, Vol. 2, No. 2, 2007, pp. 83-93. Copyright © 2013 SciRes. AJOR