[1] S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, in "Proc. 38th Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1997, pp. 554-563.

[2] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, "J. ACM", 41, 1994, pp. 153-180.

[3] J., Chen, D.K. Friesen, and H. Zheng, Tight bound on Johnson's algorithm for Max-SAT, in "Proc. 12th Annual IEEE Conference Computational Complexity", 1997, pp. 274-281.

[4] N. Chiba, T. Nishizeki, and N. Saito, An approximation algorithm for the maximum independent set problem on planar graphs, "SIAM J. Algebraic and Discrete Methods", 3, 1982, pp. 229-240.

[5] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976.

[6] V. Chvatal, A greedy heuristic for the set covering problem, "Mathematics of Operations Research", 4, 1979, pp. 233-235.

[7] W. Fernandez de la Vega and G.S. Lueker, Bin packing can be solved within 1+e in linear time, "Combinatorica", 1, 1981, pp. 349-355.

[8] H.N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, in "Proc. 1st Annual ACM-SIAM Symposium on Discrete Algorithms", ACM-SIAM, 1990, pp. 434-443.

[9] M.R. Garey, R.L. Graham, and J.D. Ullman, Worst case analysis of memory allocation algorithms, in "Proc. 4th ACM Symposium on Theory of Computing", ACM, 1972, pp. 143-150.

[10] M.R. Garey and D.S. Johnson, The complexity of near optimal graph coloring, "J. ACM", 23, 1976, pp. 43-49.

[11] M.R. Garey and D.S. Johnson, Approximation algorithms for combinatorial problems: an annotated bibliography, in "Algorithms and Complexity: New Directions and Recent Results", Academic Press, New York, 1976, pp. 41-52.

[12] M.M. Halldorsson, A still better performance guarantee for approximate graph coloring, "Information Processing Letters", 45, 1993, pp. 19-23.

[13] E. Horowitz and S.K. Sahni, Fundamentals of Computer Algorithms, Pitman, 1978.

[14] O.H. Ibarra and C.E. Kim, Fast approximation for the knapsack and sum of subset problems, "J. ACM", 22, 1975, pp. 463-468.

[15] N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem, in "Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science", IEEE Computer Society, 1982, pp. 312-320.

[16] V.K. Korobkov and R.E. Krichevskii, Algorithms for the Traveling Salesman Problem, Nauka, 1966.

[17] R.J. Lipton and R.E. Tarjan, Applications of a planar separator theorem, "SIAM J. Computing", 9, 1980, pp. 615-627.

[18] R. Motwani, Lecture notes on approximation algorithms, vol. I, Technical report, Department of Computer Science, Stanford University, 1992.

[19] R.G. Nigmatullin, Approximate algorithms with bounded absolute errors for discrete extremal problems, "Kibernetika", 1, 1976, pp. 95-101.

[20] C.H. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two, "Mathematics of Operations Research", 18, 1993, pp. 1-11.

[21] S. Sahni, On the knapsack and other computationally related problems, PhD thesis, Cornell University, 1973.

[22] P. Vaidya, Geometry helps in matching, in "Proc. 20th ACM Symposium on Theory of Computing", ACM, 1988, pp. 422-425.

[23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, "Diskret. Analiz", 3, 1964, pp. 23-30.