| DESIGN
OF HEURISTICS FOR THE SOLUTION OF COMPLEX PROBLEMS IN RESOURCE MANAGEMENT |
Non-Approximability Results
[1] S. Arora, The approximability of NP-hard problems,
in "Proc. 30th ACM Symposium on Theory of Computing", ACM, 1998,
pp. 337-348.
[2] S. Arora and C. Lund, Hardness of approximations, in Approximation Algorithms for NP-hard Problems, PWS, Boston, Mass., 1996, pp. 399-446.
[3] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, in "Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1992, pp. 14-23.
[4] S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP, "J. ACM", 45, 1998, pp. 70-122.
[5] G. Ausiello, A. D'Atri, and M. Protasi, Lattice theoretic ordering properties for NP-complete optimization problems, "Annales Societatis Mathematicae Polonae", 4, 1981, pp. 83-94.
[6] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability - towards tight results, "SIAM J. Computing", 27, 1998, pp. 804-915.
[7] P. Crescenzi, A short guide to approximation preserving reductions, in "Proc. 12th Annual IEEE Conference on Computational Complexity", IEEE Computer Society, 1997, pp. 262-273.
[8] P. Crescenzi, V. Kann, R. Silvestri and L. Trevisan, Structure in approximation classes, "SIAM J. Computing", 28, 1999, pp. 1759-1782.
[9] P. Crescenzi and A. Panconesi, Completeness in approximation classes, "Information and Computation", 93, (1991), pp. 241-262.
[10] P. Crescenzi, R. Silvestri, and L. Trevisan, To weight or not to weight: Where is the question?, in "Proc. 4th Israel Symposium on Theory of Computing and Systems", IEEE Computer Society, 1996, pp. 68-77.
[11] P. Crescenzi and L. Trevisan, On approximation scheme preserving reducibility and its applications, in "Proc. 14th Annual Conference on Foundations of Software Technology and Theoretical Computer Science", Lecture Notes in Computer Science 880, Springer-Verlag, Berlin, 1994, pp. 330-341.
[12] O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudo-Randomness, Springer-Verlag, Berlin, 1999.
[13] S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, On syntactic versus computational views of approximability, "SIAM J. Computing", 28, 1999, pp. 164-191.
[14] P.G. Kolaitis and M.N. Thakur, Logical definability of NP optimization problems, "Information and Computation", 115, 1994, pp. 321-353.
[15] P. Orponen and H. Mannila, On approximation preserving reductions: Complete problems and robust measures, Technical Report C-1987-28, Department of Computer Science, University of Helsinki, 1987.
[16] A. Panconesi and D. Ranjan, Quantifiers and approximation, "Theoretical Computer Science", 107, 1993, pp. 145-163.
[17] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, "J. Computer and System Sciences", 43, 1991, pp. 425-440.
[18] L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson, Gadgets, approximation, and linear programming, in "Proc. 37th Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1996, pp. 617-626.
[2] S. Arora and C. Lund, Hardness of approximations, in Approximation Algorithms for NP-hard Problems, PWS, Boston, Mass., 1996, pp. 399-446.
[3] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, in "Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1992, pp. 14-23.
[4] S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP, "J. ACM", 45, 1998, pp. 70-122.
[5] G. Ausiello, A. D'Atri, and M. Protasi, Lattice theoretic ordering properties for NP-complete optimization problems, "Annales Societatis Mathematicae Polonae", 4, 1981, pp. 83-94.
[6] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability - towards tight results, "SIAM J. Computing", 27, 1998, pp. 804-915.
[7] P. Crescenzi, A short guide to approximation preserving reductions, in "Proc. 12th Annual IEEE Conference on Computational Complexity", IEEE Computer Society, 1997, pp. 262-273.
[8] P. Crescenzi, V. Kann, R. Silvestri and L. Trevisan, Structure in approximation classes, "SIAM J. Computing", 28, 1999, pp. 1759-1782.
[9] P. Crescenzi and A. Panconesi, Completeness in approximation classes, "Information and Computation", 93, (1991), pp. 241-262.
[10] P. Crescenzi, R. Silvestri, and L. Trevisan, To weight or not to weight: Where is the question?, in "Proc. 4th Israel Symposium on Theory of Computing and Systems", IEEE Computer Society, 1996, pp. 68-77.
[11] P. Crescenzi and L. Trevisan, On approximation scheme preserving reducibility and its applications, in "Proc. 14th Annual Conference on Foundations of Software Technology and Theoretical Computer Science", Lecture Notes in Computer Science 880, Springer-Verlag, Berlin, 1994, pp. 330-341.
[12] O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudo-Randomness, Springer-Verlag, Berlin, 1999.
[13] S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, On syntactic versus computational views of approximability, "SIAM J. Computing", 28, 1999, pp. 164-191.
[14] P.G. Kolaitis and M.N. Thakur, Logical definability of NP optimization problems, "Information and Computation", 115, 1994, pp. 321-353.
[15] P. Orponen and H. Mannila, On approximation preserving reductions: Complete problems and robust measures, Technical Report C-1987-28, Department of Computer Science, University of Helsinki, 1987.
[16] A. Panconesi and D. Ranjan, Quantifiers and approximation, "Theoretical Computer Science", 107, 1993, pp. 145-163.
[17] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, "J. Computer and System Sciences", 43, 1991, pp. 425-440.
[18] L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson, Gadgets, approximation, and linear programming, in "Proc. 37th Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1996, pp. 617-626.
