next up previous
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.



Viggo Kann
1998-10-31