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