Scientific Research

An Academic Publisher

Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems

__Download as PDF__(Size:299KB) PP. 279-288

**Author(s)**Leave a comment

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*.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

*American Journal of Operations Research*, Vol. 3 No. 2, 2013, pp. 279-288. doi: 10.4236/ajor.2013.32025.

[1] | S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, “Proof Verification and Intractability of Approximation Problems,” Journal of the ACM, Vol. 45, No. 3, 1998, pp. 501-555. doi:10.1145/278298.278306 |

[2] | O. Goldreich, S. Goldwasser and D. Ron, “Property Testing and Its Connection to Learning and Approximation Abstract,” Journal of the ACM, Vol. 45, No. 4, 1998, pp. 653-750. doi:10.1145/285055.285060 |

[3] | O. Goldreich and M. Sudan, “Locally Testable Codes and PCPs of Almost-Linear Length,” Journal of the ACM, Vol. 53, No. 4, 2006, pp. 558-655. doi:10.1145/1162349.1162351 |

[4] | M. X. Goemans and D. P. Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,” 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 Approximation Algorithms for MAX-CUT and MAX-2SAT,” Proceedings of ACM Symposium on the Theory of Computing (STOC), 1994, pp. 422-431. |

[6] | J. Hastad, “Some Optimal Inapproximability Results,” Journal of the ACM, Vol. 48, No. 4, 2001, pp. 798-859. doi:10.1145/502090.502098 |

[7] | J. Hastad, “Complexity Theory, Proofs and Approximation,” European Congress of Mathematics, Stockholm, 2005. |

[8] | J. Hastad, “On the Efficient Approximability of Constraint Satisfaction Problems,” In: A. Hilton and J. Talbot, Eds., Surveys in Combinatorics 2007, London Mathematical Society Lecture Notes Series (No. 346), Cambridge University Press, Cambridge, 2007, pp. 201-222. doi:10.1017/CBO9780511666209.008 |

[9] | U. Feige, “A Threshold of lnn for Approximating Set Cover,” Journal of the ACM, Vol. 45, No. 4, 1998, pp. 634-652. doi:10.1145/285055.285059 |

[10] | U. Feige and G. Schechtman, “On the Integrality Ratio of Semidefinite Relaxations of MAX CUT,” In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 433-442. |

[11] | S. Khot, “On the Power of Unique 2-Prover 1-Round Games,” In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 767-775. |

[12] | S. Khot and O. Regev, “Vertex Cover Might be Hard to Approximate to within 2 ? ε,” Journal of Computer and System Sciences, Vol. 74, No. 3, 2008, pp. 335-349. doi:10.1016/j.jcss.2007.06.019 |

[13] | 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 |

[14] | S. Khot, “On the Unique Games Conjecture,” Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, 9-12 June 2010, pp. 99- 121. |

[15] | A. Samorodnitsky and L. Trevisan, “Gowers Uniformity, Influence of Variables, and PCPs,” In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 11-20. |

[16] | S. Chawla, R. Krauhgamer, R. Kumar, Y. Rabani and D. Sivakumar, “On the hardness of approximating multicut and sparsest-cut,” Proceedings of the 20th Annual IEEE Conference on Computational Complexity, San Jose, 11- 15 June 2005, pp. 144-153. doi:10.1109/CCC.2005.20 |

[17] | P. Austrin, “Balanced Max 2-Sat Might Not be the Hardest,” Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, 11-13 June 2007, pp. 189-197. |

[18] | P. Austrin, “Towards Sharp Inapproximability for Any 2- CSP,” In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington DC, 2007, pp. 307-317. |

[19] | M. Lewin, D. Livnat and U. Zwick, “Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems,” Lecture Notes in Computer Science, Vol. 2337, 2002, pp. 67-82. doi:10.1007/3-540-47867-1_6 |

[20] | G. Ausiello, B. Escoffier, J. Monnot and V. Th. Paschos, “Reoptimization of Minimum and Maximum Traveling Salesman’s Tours,” Lecture Notes in Computer Science, Vol. 4059, 2006, pp. 196-207. doi:10.1007/11785293_20 |

[21] | H.J. Bockenhauer, L. Forlizzi, J. Hromkovic, et al., “On the Approximability of TSP on Local Modifications of Optimal Solved Instances,” Algorithmic Operations Research, Vol. 2, No. 2, 2007, pp. 83-93. |

[22] | H.-J. Bockenhauer, J. Hromkovic, T. Momke and P. Widmayer, “On the Hardness of Reoptimization,” Lecture Notes in Computer Science, Vol. 4910, 2008, pp. 50-65. |

[23] | B. Escoffier, M. Milanic and V. Th. Paschos, “Simple and fast Reoptimizations for the Steiner Tree Problem,” Lamsade (Techn. Rep.) Univ. Paris Dauphin, Vol. 245, 2007. |

[24] | C. Archetti, L. Bertazzi and M. G. Speranza, “Reoptimizing the Travelling Salesman Problem,” Networks, Vol. 42, No. 3, 2003, pp. 154-159. doi:10.1002/net.10091 |

[25] | G. Ausiello, V. Bonifacci and B. Escoffier, “Complexity and Approximation in Reoptimization,” In: S. B. Cooper and A. Sorbi, Eds., Computability in Context: Computation and Logic in the Real World, Imperial College Press, London, 2011, pp. 101-130. |

[26] | V. A. Mikhailyuk, “Reoptimization of Set Covering Problems,” Cybernetics and Systems Analysis, Vol. 46, No. 6, 2010, pp. 879-883. doi:10.1007/s10559-010-9269-z |

[27] | V. A. Mikhailyuk, “General Approach to Estimating the Complexity of Postoptimality Analysis for Discrete Optimization Problems,” Cybernetics and Systems Analysis, Vol. 46, No. 2, 2010, pp. 290-295. doi:10.1007/s10559-010-9206-1 |

[28] | G. Hast, “Beating a Random Assignment,” Doctoral Thesis, Royal Institute of Technology, Stockholm, 2005. |

[29] | U. Zwick, “Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint,” In: Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 1998, pp. 551-560. |

[30] | P. Raghavendra, “Optimal Algorithms and Inapproximability Results for Every CSP?” In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 245-254. |

[31] | P. Raghavendra and D. Steurer, “How to Round Any CSP?” In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington DC, 2009, pp. 586-594. |

[32] | P. Raghavendra and D. Steurer, “Towards Computing the Grothendieck Constant,” Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 2009, pp. 525-534. |

Copyright © 2018 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.