Next: About this document ... Up: How to find the Previous: Conclusion

## Bibliography

1
  Arora, S., and Lund, C. (1997),
  Hardness of approximations,
  In Hochbaum, D. S., ed.,
  Approximation Algorithms for NP-hard Problems,
  chapter 10,
  PWS Publishing Company,
  Boston.

2
  Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999),
  Approximate solution of NP-hard optimization problems,
  Springer-Verlag,
  To appear.

3
  Bertsimas, D., Teo, C-P., and Vohra, R. (1996),
  ``On dependent randomized rounding algorithms'',
  Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization,
  Lecture Notes in Comput. Sci. 1084,
  Springer-Verlag,
  330-344.

4
  Crescenzi, P., Kann, V., Silvestri, R., and Trevisan, L. (1995),
  ``Structure in approximation classes'',
  Proc. 1st Ann. Int. Conf. on Computing and Combinatorics,
  Lecture Notes in Comput. Sci. 959,
  Springer-Verlag,
  539-548.

5
  Feige, U., and Goemans, M. X. (1995),
  ``Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT'',
  Proc. 3rd Israel Symp. on Theory of Computing and Systems,
  IEEE Computer Society,
  182-189.

6
  Garey, M. R., and Johnson, D. S. (1979),
  Computers and Intractability: a guide to the theory of NP-completeness,
  W. H. Freeman and Company,
  San Francisco.

7
  Håstad, J. (1997),
  ``Some optimal inapproximability results'',
  Proc. 29th Ann. ACM Symp. on Theory of Comp.,
  ACM,
  1-10.

8
  Holyer, I. (1981),
  ``The NP-completeness of edge-coloring'',
  SIAM J. Comp. 10,
  718-720.

9
  Johnson, D. S. (1974),
  ``Approximation algorithms for combinatorial problems'',
  J. Comput. System Sci. 9,
  256-278.

10
  Kann, V., and Panconesi, A. (1997),
  ``Hardness of approximation'',
  In Dell'Amico, M., Maffioli, F., and Martello, S., ed., Annotated Bibliographies in Combinatorial Optimization, chapter 2, Wiley, 13-30.

11
  Nishizeki, T., and Kashiwagi, K. (1990),
  ``On the 1.1 edge-coloring of multigraphs'',
  SIAM J. Disc. Math. 3,
  391-410.

12
  Petrank, E. (1994),
  ``The hardness of approximation: gap location'',
  Computational Complexity 4,
  133-157.

13
  Raz, R., and Safra, S. (1997),
  ``A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP'',
  Proc. 29th Ann. ACM Symp. on Theory of Comp.,
  ACM,
  475-484.

14
  Vizing, V. G. (1964),
  ``On an estimate of the chromatic class of a p-graph'',
  Diskret. Analiz. 3,
  23-30.