Back
 AJOR  Vol.3 No.2 , March 2013
Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems
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.
Cite this paper: V. Mikhailyuk, "Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems," American Journal of Operations Research, Vol. 3 No. 2, 2013, pp. 279-288. doi: 10.4236/ajor.2013.32025.
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.

 
 
Top