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 .
KeywordsC-Approximation AlgorithmReoptimizationApproximation Resistant PredicatesIntegrality GapUnique Games Conjecture (UGC)
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
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
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
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
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.
J. Hastad, “Some Optimal Inapproximability Results,” Journal of the ACM, Vol. 48, No. 4, 2001, pp. 798-859. doi:10.1145/502090.502098
J. Hastad, “Complexity Theory, Proofs and Approximation,” European Congress of Mathematics, Stockholm, 2005.
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
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
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.
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.
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
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
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.
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.
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
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.
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.
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
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
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.
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.
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.
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
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.
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
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
G. Hast, “Beating a Random Assignment,” Doctoral Thesis, Royal Institute of Technology, Stockholm, 2005.
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.
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.
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.
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.