approx.bib

@comment{{This file has been generated by bib2bib 1.97}}

@comment{{Command line: /usr/bin/bib2bib --expand -ob approx.bib -oc approx-list.bib ../all-entries.bib ./bib-gualandi.bib -c 'keywords : "graph coloring problem"' -c 'keywords : "approximation results"'}}

@unpublished{AchNao05,
  title = {The Two Possible Values of the Chromatic Number of a Random Graph},
  author = {D. Achlioptas and A. Naor},
  note = {To appear in \emph{Annals of Mathematics}},
  year = {2005},
  keywords = {graph coloring problem, approximation results}
}

@article{BelGolSud98,
  title = {Free Bits, {PCP}s, and Nonapproximability---Towards Tight Results},
  author = {Mihir Bellare and Oded Goldreich and Madhu Sudan},
  journal = {SIAM Journal on Computing},
  year = {1998},
  number = {3},
  pages = {804--915},
  volume = {27},
  doi = {10.1137/S0097539796302531},
  issn = {0097-5397},
  keywords = {graph coloring problem, approximation results},
  publisher = {Society for Industrial and Applied Mathematics}
}

@article{BerRom90,
  title = {A better performance guarantee for approximate graph colouring},
  author = {B. Berger and J. Rompel},
  journal = {Algorithmica},
  year = {1990},
  number = {4},
  pages = {459--466},
  volume = {5},
  keywords = {graph coloring problem, approximation results}
}

@article{OghTar04,
  title = {Exact and approximative algorithms for coloring G(n, p).},
  author = {Amin Coja-Oghlan and Anusch Taraz},
  journal = {Random structures \& algorithms},
  year = {2004},
  number = {3},
  pages = {259-278},
  volume = {24},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {10.1002/rsa.20007},
  keywords = {graph coloring problem, approximation results}
}

@misc{CreVig04,
  title = {A compendium of {NP} optimization problems},
  author = {P.~Crescenzi and K.~Viggo},
  note = {Available online (last visited February 2005)},
  year = {2004},
  keywords = {graph coloring problem, approximation results},
  url = {http://www.nada.kth.se/\tld viggo/problemlist/compendium.html}
}

@article{FeiKil98,
  title = {Zero Knowledge and the Chromatic Number},
  author = {Uriel Feige and Joe Kilian},
  journal = {Journal of Computer and System Sciences},
  year = {1998},
  number = {2},
  pages = {187--199},
  volume = {57},
  keywords = {graph coloring problem, approximation results}
}

@inproceedings{GomRegShm03,
  title = {An Improved Approximation for the Partial Latin Square Extension Problem},
  author = {Carla Gomes and Rommel Regis and David Shmoys},
  booktitle = {Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2003},
  address = {Baltimore, Maryland, USA},
  keywords = {graph coloring problem, approximation results}
}

@article{Hal93,
  title = {A still better performance guarantee for approximate graph coloring},
  author = {Magn\'us M. Halld\'orsson},
  journal = {Information Processing Letters},
  year = {1993},
  number = {1},
  pages = {19--23},
  volume = {45},
  doi = {10.1016/0020-0190(93)90246-6},
  issn = {0020-0190},
  keywords = {graph coloring problem, approximation results},
  publisher = {Elsevier North-Holland, Inc.}
}

@article{Joh74:a,
  title = {Approximation Algorithms for Combinatorial Problems},
  author = {D. S. Johnson},
  journal = {Journal of Computer and System Sciences},
  year = {1974},
  pages = {256--278},
  volume = {9},
  keywords = {graph coloring problem, approximation results}
}

@article{Pas70,
  title = {Polynomial approximation and graph-coloring},
  author = {V. Th. Paschos},
  journal = {Computing},
  year = {2003},
  number = {1},
  pages = {41--86},
  volume = {70},
  doi = {10.1007/s00607-002-1468-7},
  issn = {0010-485X},
  keywords = {graph coloring problem, approximation results},
  publisher = {Springer}
}

@article{Wig83,
  title = {Improving the performance guarantee for approximate graph coloring},
  author = {Avi Wigderson},
  journal = {Journal of the ACM},
  year = {1983},
  number = {4},
  pages = {729--735},
  volume = {30},
  doi = {http://doi.acm.org/10.1145/2157.2158},
  issn = {0004-5411},
  keywords = {graph coloring problem, approximation results},
  publisher = {ACM Press, New York, NY, USA}
}

@inproceedings{W82,
  title = {A new approximate graph coloring algorithm},
  author = {Avi Wigderson},
  booktitle = {Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing},
  year = {1982},
  pages = {325-329},
  keywords = {graph coloring problem, approximation results}
}