Next: About this document ...
Up: How to find the
Previous: Conclusion
-
- 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