% The Chicago Journal of Theoretical Computer Science, Volume 1997, Article 2
% Bibliography

@InProceedings{cj97-02-01,
  author =       {S. Arora and D. Karger and M. Karpinski},
  title =        {Polynomial time approximation schemes for dense
                 instances of {NP}-hard problems},
  booktitle =    {Proceedings of the 27th Annual ACM Symposium on
                  Theory of Computing},
  publisher =    {ACM},
  year =         {1995},
  pages =        {284--293}
}

@InProceedings{cj97-02-02,
  author =       {M. Bellare and O. Goldreich and M. Sudan},
  title =        {Free bits, {PCP}s and non-approximability---towards
                 tight results},
  booktitle =    {Proceedings of the 36th Annual IEEE Symposium on
                  Foundations of Computer Science},
  year =         {1995},
  pages =        {422--431},
  publisher =    {IEEE}
}

@TechReport{cj97-02-03,
  author =       {P. Crescenzi and V. Kann},
  year =         {1995},
  title =        {A compendium of {NP} optimization problems},
  institution =  {Dipartimento di Scienze dell'Informazione,
                 Universit\`a di Roma ``La Sapienza''},
  number =       {SI/RR-95/02},
  note =         {The list is updated continuously. The latest version
                 is available at {\small\tt
                 http://www.nada.kth.se/theory/problemlist.html}}
}

@InProceedings{cj97-02-04,
  author =       {P. Crescenzi and V. Kann and R. Silvestri and L.
                 Trevisan},
  year =         {1995},
  title =        {Structure in approximation classes},
  booktitle =    {Proceedings of the 1st Annual International
                  Conference on Computing and Combinatorics},
  series =       {Lecture Notes in Computer Science},
  volume =       {959},
  publisher =    {Springer-Verlag},
  pages =        {539--548}
}

@InProceedings{cj97-02-05,
  author =       {P. Crescenzi and R. Silvestri and L. Trevisan},
  title =        {To weight or not to weight: Where is the question?},
  booktitle =    {Proceedings of the 4th Israel Symposium on Theory of
                  Computing and Systems},
  year =         {1995},
  pages =        {66--77},
  publisher =    {IEEE}
}

@Article{cj97-02-06,
  author =       {K. Edwards},
  title =        {The complexity of colouring problems},
  journal =      {Theoretical Computer Science},
  volume =       {43},
  year =         {1986},
  pages =        {337--343}
}

@InProceedings{cj97-02-07,
  author =       {A. Frieze and M. Jerrum},
  title =        {Improved approximation algorithms for {MAX} $k$-{CUT}
                 and {MAX BISECTION}},
  year =         {1995},
  booktitle =    {Proceedings of the 4th International Conference on
                  Integer Programming and Combinatorial Optimization},
  series =       {Lecture Notes in Computer Science},
  volume =       {920},
  publisher =    {Springer-Verlag},
  pages =        {1--13}
}

@Article{cj97-02-08,
  author =       {N. Garg and V. V. Vazirani and M. Yannakakis},
  title =        {Approximate max-flow min-(multi)cut theorems and their
                 applications},
  journal =      {SIAM Journal on Computing},
  volume =       {25},
  year =         {1996},
  pages =        {235--251}
}

@Article{cj97-02-09,
  author =       {M. X. Goemans and D. P. Williamson},
  title =        {Improved Approximation Algorithms for Maximum Cut and
                 Satisfiability Problems Using Semidefinite
                 Programming},
  journal =      {Journal of the ACM},
  volume =       {42},
  year =         {1995},
  pages =        {1115--1145}
}

@InProceedings{cj97-02-10,
  author =       {J. H{\aa}stad},
  title =        {Some optimal inapproximability results},
  year =         {1997},
  booktitle =    {Proceedings of the 29th Annual ACM Symposium on
                  Theory of Computing},
  publisher =    {ACM},
  pages =        {1--10}
}

}

@Book{cj97-02-11,
  author =       {R. Motwani and P. Raghavan},
  title =        {Randomized Algorithms},
  publisher =    {Cambridge University Press},
  year =         {1995}
}

@Article{cj97-02-12,
  author =       {C. H. Papadimitriou and M. Yannakakis},
  title =        {Optimization, approximation, and complexity classes},
  journal =      {Journal of Computing and System Sciences},
  volume =       {43},
  year =         {1991},
  pages =        {425--440}
}

@Article{cj97-02-13,
  author =       {E. Petrank},
  title =        {The hardness of approximation: Gap location},
  journal =      {Computational Complexity},
  pages =        {133--157},
  volume =       {4},
  year =         {1994}
}

@InCollection{cj97-02-14,
  author =       {S. Poljak and Z. Tuza},
  title =        {Maximum cuts and largest bipartite subgraphs},
  booktitle =    {Combinatorial Optimization},
  series =       {DIMACS: Series in Discrete Mathematics and
                  Theoretical Computer Science},
  volume =       {20},
  year =         {1995},
  editor =       {W. Cook and L. Lov{\'a}sz and P. Seymour},
  publisher =    {American Mathematical Society}
}

@Article{cj97-02-15,
  author =       {P. Tur{\'a}n},
  year =         {1941},
  journal =      {Matematikai Fizikai Lapok},
  title =        {An extremal problem in graph theory},
  pages =        {436--452},
  volume =       {48},
  note =         {Written in Hungarian}
}

@Book{cj97-02-16,
  author =       {D. B. West},
  title =        {Introduction to Graph Theory},
  publisher =    {Prentice-Hall Inc.},
  address =      {NJ},
  year =         {1996}
}