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.

DOI: 10.4236/ajor.2013.32025                

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.

Keywords

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

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