% 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}
}