%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ToC#239 v002/a013.bib  Giotis - Guruswami 10-19-2006 11pm version
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%\usepackage{eprint}

@inproceedings(ACN,
author="N. Ailon and M. Charikar and A. Newman",
title="Aggregating {I}nconsistent {I}nformation: {R}anking and {C}lustering",
booktitle="Proc. 37th STOC",
pages="684--693",
publisher="ACM Press",
year=2005,
eprint={stoc:1060590.1060692})

@Inproceedings(ABHKS,
author="S. Arora and E. Berger and E. Hazan and G. Kindler and S. Safra",
title="On Non-Approximability for Quadratic Programs",
booktitle="Proc. 46th FOCS",
publisher="IEEE Computer Society Press",
year=2005,
pages="206--215",
eprint={focs:10.1109/SFCS.2005.57})

@article(NRT,
author="A. Nemirovski and C. Roos and T. Terlaky",
title="On maximization of quadratic form over intersection of ellipsoids with common center",
journal="Mathematical Programming",
volume=86,
number=3,
pages="463--473",
year=1999,
eprint={stacs:922f1ftd6bpfxhk7})

@inproceedings(ACMM,
author="A. Agarwal and M. Charikar and K. Makarychev and Y. Makarychev",
title="${O}(\sqrt{\log n})$ approximation algorithms for {M}in {U}nCut, {M}in 2{CNF} Deletion, and directed cut problems",
booktitle="Proc. 37th STOC",
publisher="ACM Press",
year=2005,
pages="573--581",
eprint={stoc:10.1145/1060590.1060675})

@article(KPRT,
author="P. Klein and S. Plotkin and S. Rao and E. Tardos",
title="Approximation algorithms for Steiner and directed multicuts",
journal="Journal of Algorithms",
volume=22,
number=2,
pages="241--269",
year=1997,
eprint={10.1006/jagm.1996.0833})

@inproceedings(indyk,
author="P. Indyk",
title="A Sublinear-time Approximation Scheme for Clustering in Metric Spaces",
booktitle="Proc. 40th FOCS",
publisher="IEEE Computer Society Press",
year=1999,
pages="154--159",
eprint={focs:10.1109/SFFCS.1999.814587})

@inproceedings(AMMN,
author="N. Alon and K. Makarychev and Y. Makarychev and A. Naor",
title="Quadratic forms on graphs",
booktitle="Proc. 37th STOC",
publisher="ACM Press",
year=2005,
pages="486--493",
eprint={stoc:10.1145/1060590.1060664})

@Inproceedings(dVKKR,
author="W. {Fernandez de la Vega} and M. Karpinski and C. Kenyon and Y. Rabani",
title="Approximation Schemes for Clustering Problems",
booktitle="Proc. 35th STOC",
publisher="ACM Press",
year=2003,
pages="50--58",
eprint={stoc:10.1145/780542.780550})

@inproceedings(vega-kenyon,
author="W. {Fernandez de la Vega} and C. Kenyon",
title="A Randomized Approximation Scheme for Metric MAX-CUT",
booktitle="Proc. 39th FOCS",
publisher="IEEE Computer Society Press",
pages="468--471",
year=1998,
eprint={focs:10.1109/SFCS.1998.743497})


@article(CGW,
author="M. Charikar and V. Guruswami and A. Wirth",
title="Clustering with qualitative information",
journal="Journal of Computer and System Sciences",
volume=71,
number=3,
month="October",
year=2005,
pages="360--383",
eprint={jcss:10.1016/j.jcss.2004.10.012})

@inproceedings(CGW-focs,
author="M. Charikar and V. Guruswami and A. Wirth",
title="Clustering with qualitative information",
booktitle="Proc. 44th FOCS",
publisher="IEEE Computer Society Press",
pages="524--533",
year=2003)

@inproceedings(CW,
author="M. Charikar and A. Wirth",
title="Maximizing quadratic programs: extending {Grothendieck's} inequality",
booktitle="Proc. 45th FOCS",
publisher="IEEE Computer Society Press",
year=2004,
pages="54--60",
eprint={focs:10.1109/FOCS.2004.39})

@article(GGR,
author="O. Goldreich and S. Goldwasser and D. Ron",
title="Property testing and its connection to learning and approximation",
journal="Journal of the ACM",
volume=45,
number=4,
pages="653--750",
month="July",
year=1998,
eprint={jacm:10.1145/285055.285060})

@inproceedings(KKMO,
author="S. Khot and G. Kindler and E. Mossel and R. O'Donnell",
title="Optimal inapproximability results for {Max Cut} and other 2-variable {CSP}s",
booktitle="Proc. 45th FOCS",
publisher="IEEE Computer Society Press",
year=2004,
pages="146--154",
eprint={focs:10.1109/FOCS.2004.49})


@inproceedings{gramm,
author = "J. Gramm and J. Guo and F. H{\"u}ffner and R. Niedermeier",
title = "Graph-Modeled Data  Clustering: Fixed-Parameter Algorithms for
Clique Generation",
booktitle = "Proc. 5th Italian Conf. on Algorithms and Complexity (CIAC'03)",
year = 2003,
pages = "108--19",
eprint={ciac:wfqd4c5405fddh8j}
}

@inproceedings(SST,
author="R. Shamir and R. Sharan and D. Tsur",
title="Cluster graph modification problems",
booktitle="Proc. 28th Workshop on Graph Theory (WG'02)",
year= 2002,
pages="379--390"
)

@article(BSY,
author="A. Ben-Dor and R. Shamir and Z. Yakhini",
title="Clustering gene expression patterns",
journal="Journal of Computational Biology",
volume=6,
pages="281--297",
year=1999)

@incollection(roberts,
author = "F. Roberts",
title = "Discrete Mathematics",
booktitle = "Int. Encyc. Social and Behavioral Sciences",
pages = "3743--3746",
year = 2001,
publisher = "Elsevier"
)

@inproceedings(swamy,
author = "C. Swamy",
title = "Correlation {C}lustering: {M}aximizing Agreements via Semidefinite Programming",
booktitle="Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA'04)",
publisher="SIAM",
pages="519--520",
year = 2004,
eprint={soda:982866}
)

@article(BBC,
author = "N. Bansal and A. Blum and S. Chawla",
title = "Correlation Clustering",
journal="Machine Learning, Special Issue on Clustering",
year=2004,
volume=56,
pages="89--113",
doi={10.1023/B:MACH.0000033116.57574.95}
)


@article(kss,
author = "M. Kearns and R. Schapire and L. Sellie",
title = "Toward efficient agnostic learning",
journal = "Machine Learning",
year = 1994,
pages = "115--142",
volume = 17,
doi={10.1007/BF00993468}
)

@article(ensz,
author = "G. Even and J. Naor and B. Schieber and L. Zosin",
title = "Approximating Minimum Subset Feedback Sets in Undirected Graphs
with Applications",
journal = "SIAM J. Discrete~Math.",
year = 2000,
pages = "255--267",
volume = 25
)

@article(GVY,
author = "N. Garg and V. Vazirani and M. Yannakakis",
title = "Approximate Max-Flow Min-(multi)cut Theorems and Their Applications.",
journal = "SIAM J. Computing",
year = 1996,
pages = "235--251",
volume = 25
)

@article(hastad,
author = "J. H{\aa}stad",
title = "Some optimal inapproximability results",
journal = "Journal of the ACM",
year = 2001,
pages = "798--859",
volume = 48
)

@article(GVY2,
author = "N. Garg and V. Vazirani and M. Yannakakis",
title = "Primal-dual approximation algorithms
for integral flow and multicut in trees",
journal = "Algorithmica",
year = 1997,
pages = "3--20",
volume = 18
)

@article(CKR00,
author = "G. Calinescu and H. Karloff and Y. Rabani",
title =  "An Improved Approximation Algorithm for Multiway Cut",
journal = "J. Computer and System Sciences",
year = 2000,
pages = "564--574",
volume = 60
)

@inproceedings(KKS+99,
author = "D. Karger and P. Klein and C. Stein and M. Thorup and N. Young",
title =  "Rounding Algorithms for a Geometric Embedding of Minimum Multiway
Cut",
booktitle = "Proc. 31st STOC",
publisher="ACM Press",
year = 1999,
pages = "668--678"
)

@inproceedings(nickle,
author = "E. Demaine and N. Immorlica",
title = "Correlation Clustering with Partial Information",
booktitle = "Proc. 6th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'03)",
publisher="Springer",
series="LNCS",
volume=2764,
isbn={3-540-40770-7},
year = 2003,
pages = "1--13",
doi={10.1007/b11961}
)

@article(KRAR,
author="P. Klein and S. Rao and A. Agarwal and R. Ravi",
title="An approximate max-flow min-cut relation for multicommodity flow, with applications",
journal="Combinatorica",
volume=15,
year=1995,
pages="187--202")

@inproceedings(dotan,
author = "D. Emanuel and A. Fiat",
title = "Correlation Clustering---Minimizing
Disagreements on Arbitrary Weighted Graphs",
booktitle = "Proc. 11th European Symp. on Algorithms ({ESA'03})",
publisher="Springer",
year = 2003,
pages = "208--220",
doi={10.1007/b13632}
)

@article(setsplitting,
author = "V. Guruswami",
title = "Inapproximability results for set splitting and satisfiability problems with no mixed clauses",
journal="Algorithmica",
volume=38,
number=3,
pages="451--469",
month="December",
year=2003)

@article(chen,
author = "Z. Chen and T. Jiang and G. Lin",
title = "Computing Phylogenetic Roots with Bounded Degrees and Errors",
journal =  "SIAM J.~Computing",
volume = 32,
number =4,
pages = "864--879",
year = 2003
)

@proceedings{DBLP:conf/approx/2000,
 editor    = {Klaus Jansen and
              Samir Khuller},
 booktitle     = {Proc. 3rd Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'00)}
 publisher = {Springer},
 series    = {Lecture Notes in Computer Science},
 volume    = {1913},
 year      = {2000},
 isbn      = {3-540-67996-0},
 bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings(khot,
author = "S. Khot",
title = "On the power of unique 2-prover 1-round games",
booktitle = "Proc.~of 34th STOC",
publisher="ACM Press",
year = 2002,
pages = "767--775"
)


@book(papadi,
author = "C. Papadimitriou",
title = "Computational Complexity",
publisher = "Addison Wesley Longman",
year = 1994
)


@book(vazirani,
author = "V. Vazirani",
title = "Approximation Algorithms",
publisher = "Springer",
year = 2001
)


@incollection(FJ,
   author = "A. Frieze and M. Jerrum",
   title = "Improved approximation algorithms for {MAX} \(k\)-{CUT} and
   {MAX} {BISECTION}",
   booktitle = "Proc.~of 4th International Conf. Integer Programming and Combinatorial Optimization",
   volume = "920",
   series = "LNCS",
   publisher = "Springer",
   editor = "E. Balas and J. Clausen",
   pages = "1--13",
   year = "1995"
)