Partial bibliography for the Course on Coping with NP-Hardness / Computational complexity

1. R. Boppana and M.M. Halldorsson. New performance guarantees for the maximum independent set and graph coloring problems. In Proc. 2nd Scandinavian Workshop on Algorithm Theory, volume LNCS-447. Springer-Verlag, July 1990.
2. V. Chvatal. A greedy heuristic for the set-covering problem. Math. of Oper. Res., 4:233--235, 1979.
3. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completness. W. H. Freeman and Co., San Francisco, CA, 1979.
4. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Oper. Res., 18:1138--1162, 1970.
5. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees: Part II. Math. Prog., 1:6--25, 1971.
6. D. S. Hochbaum. Approximation algorithms for the set covering and vertex covering problems. SIAM J. on Comput., 11(3):555--556, 1982.
7. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. of the ACM, 33(3):533--550, July 1986.
8. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Co., Reading, MA, 1979.
9. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. J. of the ACM, 21(2):277--292, April 1974.
10. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. of the ACM, 22(4):463--468, October 1975.
11. D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 9:256--278, 1974.
12. R.M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computation, pages 85--103, 1972.
13. B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Tech. Journal, pages 291--307, 1970.
14. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. The Traveling Salesman Problem. John Wiley & Sons, New York, NY, 1985.
15. Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Math. of Oper. Res., 4(4):339--356, November 1979.
16. Richard J. Lipton and Robert E. Tarjan. Applications of a planar separator theorem. SIAM J. on Comput., 9:615--627, 1980.
17. C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., 1979.
18. P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. and Syst. Sci., 37:130--143, 1988.
19. P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365--374, 1987.
20. R. Schroeppel and A. Shamir. A , algorithm for certain NP-complete problems. SIAM J. on Comput., 10:456--464, 1989.
21. Avi Wigderson. Improving the performance guarantee for approximate graph coloring. J. of the ACM, 30:729--735, 1983.
22. L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2:385--393, 1982.
23. Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM, 45:753--782, 1998.
24. Joseph S. B. Mitchell. Guillotine Subdivisions Approximate Polygonal Subdivisions: {A} Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. SIAM Journal on Computing, 28:1298--1309, 1999.