%% v002/a002 bib file

@Article{LiptakLovasz:01,
  author =  "L{\'a}szl{\'o} Lipt{\'a}k and L{\'a}szl{\'o}
         Lov{\'a}sz",
  title =   "Critical facets of the stable set polytope",
  journal = "Combinatorica",
  pages =   "61--88",
  year =    2001,
  number =  1,
  volume =  21,
  publisher =   "J{\'a}nos Bolyai Mathematical Society, Springer
         International",
  mdate =   "2005-08-18",
  eprint = {Combinatorica:8hmkpcvb5qaw5dnv},
  ps = "http://research.microsoft.com/users/lovasz/critical.ps",
}

@InProceedings{AlekhnovichAT:05,
  author =       "Mikhail Alekhnovich and Sanjeev Arora and Iannis
Tourlakis",
  title =        "Towards strong nonapproximability results in the {Lov
\'{a}sz-Schrijver} hierarchy",
  booktitle =    "Proceedings of the 37th Annual Symposium on the Theory
                 of Computing",
  month =        may,
  publisher =    "ACM Press",
  address =      "New York",
  year =         "2005",
  eprint =       {stoc:1060590.1060634},
}

@InProceedings{Tourlakis:05,
  title =        "Towards optimal integrality gaps for hypergraph
                 vertex cover in the {Lov\'asz}-{Schrijver} hierarchy",
  author =    "Iannis Tourlakis",
  year =    "2005",
  booktitle =   "8th. International Workshop on Approximation Algorithms
                for Combinatorial Optimization Problems and 9th
                International Workshop on Randomization and
Computation",
  pages =   "233--244",
  ps = "http://www.cs.princeton.edu/~itourlak/publications/approx05.ps",
}


@InProceedings{AroraBL:02,
  author =       "Sanjeev Arora and B{\'e}la Bollob{\'a}s and
                 L{\'a}szl{\'o} Lov{\'a}sz",
  title =        "Proving Integrality Gaps without Knowing the Linear
                 Program",
  pages =        "313--322",
  booktitle =    "Proceedings of the 43rd Symposium on Foundations of
                 Computer Science ({FOCS}-02)",
  month =        nov # " ~16--19",
  address =      "Los Alamitos",
  year =         2002,
  eprint =       {focs:10.1109/SFCS.2002.1181954},
}

@Article{Chvatal:73,
  author =  "Vasek Chv{\'a}tal",
  title =   "Edmonds polytopes and a hierarchy of combinatorial
         problems",
  journal = "Discrete Math.",
  pages =   "305--337",
  year =    "1973",
  volume =  "4",
  publisher =   "Elsevier Science Publishers B.V. (North Holland)",
  address = "Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
}

@Article{DinurSafra:05,
  author =       "Irit Dinur and Shmuel Safra",
  title =        "On the hardness of approximating minimum vertex
cover",
  journal =    "Annals of Mathematics",
  volume =      "162",
  number =      "1",
  year =        "2005",
  ps = "http://www.cs.huji.ac.il/~dinur/mypapers/vc.ps",
}

@Article{CookDash:01,
  author =  "William Cook and Sanjeeb Dash",
  title =   "On the matrix-cut rank of polyhedra",
  journal = "Mathematics of Operations Research",
  year =    "2001",
  volume =  "26",
  number =  "1",
  pages =   "19--30",
}

@InCollection{Hochbaum:97b,
  author =  "Dorit Hochbaum",
  title =   "Approximating Covering and Packing Problems: Set
         Cover, Vertex Cover, Independent Set, and Related
         Problems",
  booktitle =   "Approximation Algorithms for NP-hard Problems",
  publisher = "PWS     Publishing Company",
  year =    "1997",
}

@InProceedings{BureshOppenheimGHMP:03,
  author =  "Joshua Buresh-Oppenheim and Nicola Galesi and Shlomo Hoory
and Avner
         Magen and Toniann Pitassi",
  title =   "Rank bounds and integrality gaps for cutting planes
         procedures",
  booktitle =   "Proceedings: 44th Annual {IEEE} Symposium on
         Foundations of Computer Science, {FOCS} 2003, 11--14
         October 2003, Cambridge, Massachusetts",
  publisher =   "pub-IEEE",
    pages =   "318--327",
  year =    "2003",
  eprintdeprecated = {FOCS:2003.1238206},
}

@UNPUBLISHED{CheriyanQian:05,
  author =       "Joseph  Cheriyan and Fei Qian",
  note =         "Personal communication",
  year =         "2005",
}


@mastersthesis{Qian:03,
  author =       "Fei Qian",
  title =        "The integrality gap of the minimum vertex cover
problem",
  school =       "University of Waterloo",
  year =         "2003",
}

@Article{Wolsey:80,
  author =  "Laurence A. Wolsey",
  title =   "Heuristic analysis, linear programming, and branch and
         bound",
  journal = "Mathematical Programming Studies",
  volume =  "13",
  year =    "1980",
  pages =   "121--134",
}

@Article{Yannakakis:91,
  title =   "Expressing Combinatorial Optimization Problems by
         Linear Programs",
  author =  "Mihalis Yannakakis",
  pages =   "441--466",
  journal = "Journal of Computer and System Sciences",
  year =    1991,
  month =   dec,
  volume =  43,
  number =  3,
  eprint =  {JCSS:10.1016/0022-0000(91)90024-Y},
  preliminary =  "STOC::Yannakakis1988",
}

@InCollection{Shmoys:97,
  author =  "David B. Shmoys",
  title =   "Cut Problems and Their Application to
         Divide-and-Conquer",
  booktitle =   "Approximation Algorithms for NP-hard Problems",
  publisher =   "PWS Publishing Company",
  year =    "1997",
}

@Book{Vazirani:01,
  author =  "Vijay V. Vazirani",
  title =   "Approximation Algorithms",
  pages =   "xix, 378",
  year =    "2001",
  publisher =   "Springer-Verlag",
  address = "Berlin",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
}

@Article{SheraliAdams:90,
  author =  "Hanif D. Sherali and Warren P. Adams",
  title =   "A Hierarchy of Relaxations Between the Continuous and
         Convex Hull Representations for Zero-One Programming
         Problems",
  journal = "SIAM Journal on Discrete Mathematics",
  volume =  "3",
  number =  "3",
  pages =   "411--430",
  month =   aug,
  year =    "1990",
  CODEN =   "SJDMEC",
  ISSN =    "0895-4801 (print), 1095-7146 (electronic)",
  MRclass = "90C09 (90C05)",
  MRnumber =    "91k:90116",
  mrreviewer =  "Csaba Fabian",
  bibdate = "Thu Apr 9 15:20:35 MDT 1998",
  mrnumber-url = "http://www.ams.org/mathscinet-getitem?mr=91k%3a90116",
  eprint = {sidma:03/0403036},
}

@Article{Razborov:85,
  author = "Alexander A. Razborov",
  title = "Lower bounds on the monotone complexity of some {Boolean}
functions",
  journal = "Dokl. Akad. Nauk SSSR",
  volume = "281",
  number = "4",
  pages = "798--801",
  year = "1985",
  note = "In Russian: English translation in {\em Soviet Math. Dokl.}
31:354--357, 1985",
}

@Article{Erdos:59,
  author =  "Paul Erd{\"{o}}s",
  title =   "Graph Theory and Probability",
  journal = "Canadian Journal of Mathematics",
  year =    "1959",
  volume =  "11",
  pages =   "34--38",
  keywords =    "graph coloring related theory",
}

@Article{Erdos:62,
  author =  "Paul Erd{\"{o}}s",
  title =   "On Circuits and Subgraphs of Chromatic Graphs",
  journal = "Mathematika",
  year =    "1962",
  volume =  "9",
  pages =   "170--175",
  keywords =    "graph coloring related theory",
}

@Book{AlonSpencer:92,
  author =  "Noga Alon and Joel H. Spencer",
  title =   "The probabilistic method",
  publisher =   "Wiley",
  address = "New York",
  year =    "1992",
}

@InCollection{AroraLund:95,
  author =  "Sanjeev Arora and Carsten Lund",
  title =   "Hardness of Approximations",
  chapter = "10",
  year =    "1995",
  editor =  "D. S. Hochbaum",
  publisher =   "PWS",
  booktitle =   "Approximation Algorithms for NP-Hard Problems",
}

@Book{Bollobas:98,
  author =  "B{\'e}la Bollob{\'a}s",
  title =   "Modern graph theory",
  booktitle =   "Modern graph theory",
  pages =   "xiii, 394",
  year =    "1998",
  volume =  "184",
  series =  "Graduate Texts in Mathematics",
  publisher =   "Springer-Verlag",
  address = "Berlin",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
}

@Article{FeigeKrauthgamer:03,
  title =   "The Probable Value of the {Lov{\'a}sz--Schrijver}
         Relaxations for Maximum Independent Set",
  author =  "Uriel Feige and Robert Krauthgamer",
  journal = "SIAM Journal on Computing",
  year =    "2003",
  number =  "2",
  volume =  "32",
  bibdate = "2003-11-27",
  bibsource =   "DBLP,

http://dblp.uni-trier.de/db/journals/siamcomp/siamcomp32.html#FeigeK03",
  pages =   "345--370",
  url =     "http://epubs.siam.org/sam-bin/dbq/article/40118",
  eprint =  {sicomp:10.1137/S009753970240118X},
}

@Article{Feige:98,
  title =   "A Threshold of $\ln n$ for Approximating Set Cover",
  author =  "Uriel Feige",
  journal = "Journal of the ACM",
  year =    "1998",
  number =  "4",
  volume =  "45",
  bibdate = "2003-11-20",
  bibsource =   "DBLP,
         http://dblp.uni-trier.de/db/journals/jacm/jacm45.html#Feige98",
  pages =   "634--652",
  URL =     "http://doi.acm.org/10.1145/285055.285059",
  eprint =  {jacm:285055.285059},
}

@Book{Hochbaum:97,
  editor =  "Dorit Hochbaum",
  title =   "Approximation Algorithms for {NP}-hard Problems",
  publisher =   "PWS Publishing Company",
  year =    "1997",
}


@InProceedings{DinurGKR:03,
  author =       "Irit Dinur and Venkatesan Guruswami and Subhash Khot
                 and Oded Regev",
  title =        "A new multilayered {PCP} and the hardness of
                 hypergraph vertex cover",
  editor =       "{ACM}",
  booktitle =    "Proceedings of the Thirty-Fifth {ACM} Symposium on
                 Theory of Computing, San Diego, {CA}, {USA}, June
                 9--11, 2003",
  publisher =    "ACM Press",
  address =      "New York, NY, USA",
  pages =        "595--601",
  year =         "2003",
  eprint =       {stoc:780542.780629},
}

@Article{Hastad:01,
  author =  "Johan H{\aa}stad",
  title =   "Some optimal inapproximability results",
  year =    "2001",
  journal = "Journal of the ACM",
  volume =  "48",
  number =  "4",
  pages =   "798--859",
  eprint =  {jacm:258533.258536}
}

@Article{LovaszSchrijver:91,
  author =  "L\'aszl\'o Lov{\'a}sz and Alexander Schrijver",
  title =   "Cones of matrices and set-functions and $0$-$1$
         optimization",
  journal = "SIAM Journal on Optimization",
  volume =  "1",
  number =  "2",
  pages =   "166--190",
  month =   may,
  year =    "1991",
  CODEN =   "SJOPE8",
  ISSN =    "1052-6234 (print), 1095-7189 (electronic)",
  MRclass = "05C90 (90C09 90C27)",
  MRnumber =    "MR1098425 (92b:05072)",
  mrreviewer =  "D. de Werra",
  bibdate = "Tue Sep 30 16:05:25 MDT 2003",
  bibsource =   "MathSciNet database",
  mrnumber-url = "http://www.ams.org/mathscinet-getitem?mr=92b%3a05072",
  eprint =  {siopt:01/0801013},
}

@InProceedings{PapadimitriouVempala:00,
  author =  "Christos H. Papadimitriou and Santosh Vempala",
  title =   "On the approximability of the {Traveling} {Salesman}
         problem",
  booktitle =   "Proceedings of the 32nd Annual ACM Symposium on Theory
         of Computing, STOC'2000 (Portland, Oregon, May 21-23,
         2000)",
  pages =   "126--133",
  year =    "2000",
  publisher =   "ACM Press",
  address = "New York",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
  eprint =  {stoc:335305.335320}
}

@Book{GroetschelLS:93,
  author =  "Martin Gr{\"o}tschel and L{\'a}szl{\'o} Lov{\'a}sz and
         Alexander Schrijver",
  title =   "Geometric Algorithms and Combinatorial Optimization",
  booktitle =   "Geometric Algorithms and Combinatorial Optimization",
  pages =   "xii, 362",
  year =    "1993",
  volume =  "2",
  series =  "Algorithms and Combinatorics",
  publisher =   "Springer-Verlag",
  address = "Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong
         Kong-Barcelona-Budapest-Milan-Santa Clara-Singapore",
  pcomment =    "Second Corrected Edition",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
}

@Article{Goemans:95,
  author =  "Michel X. Goemans",
  title =   "Worst-case comparison of valid inequalities for the
         {TSP}",
  journal = "Mathematical Programming",
  volume =  "69",
  year =    "1995",
  pages =   "335--349",
  eprint = {MathProg:n25193135v44l625},
}

@InProceedings{GoemansWilliamson:94,
  author =  "Michel X. Goemans and David P. Williamson",
  title =   "$.878$-approximation algorithms for {MAX} {CUT} and
         {MAX} 2{SAT}",
  booktitle =   "Proceedings of the 26th Annual ACM Symposium on Theory
         of Computing, STOC'94 (Montr{\'e}al, Qu{\'e}bec,
         Canada, May 23-25, 1994)",
  pages =   "422--431",
  year =    "1994",
  publisher =   "ACM Press",
  address = "New York",
  cdate =   "1970-01-01",
  mdate =   "2005-08-18",
  eprint = {stoc:195058.195216},
}

@Article{GoemansTuncel:01,
  title =   "When Does the Positive Semidefiniteness Constraint
         Help in Lifting Procedures?",
  author =  "Michel X. Goemans and Levent Tun{\c c}el",
  journal = "Mathematics of Operations Research",
  year =    "2001",
  number =  "4",
  volume =  "26",
  bibdate = "2004-10-26",
  bibsource =   "DBLP,

http://dblp.uni-trier.de/db/journals/mor/mor26.html#GoemansT01",
  pages =   "796--815",
  URL =     "http://dx.doi.org/10.1287/moor.26.4.796.10012",
}

@Article{Feige:97,
  title =   "Randomized Graph Products, Chromatic Numbers, and the
         {Lov{\'a}sz} $\vartheta$-Function",
  author =  "Uriel Feige",
  journal = "Combinatorica",
  year =    "1997",
  number =  "1",
  volume =  "17",
  bibdate = "2002-01-03",
  bibsource =   "DBLP,

http://dblp.uni-trier.de/db/journals/combinatorica/combinatorica17.html#Feige97",
  pages =   "79--90",
  eprint = {Combinatorica:x785787h43724566}
}

@Article{BonetPR:97,
  title =   "Lower Bounds for Cutting Planes Proofs with Small
         Coefficients",
  author =  "Maria Bonet and Toniann Pitassi and Ran Raz",
  pages =   "708--728",
  journal = "The Journal of Symbolic Logic",
  year =    "1997",
  month =   sep,
  volume =  "62",
  number =  "3",
  preliminary =  "STOC::BonetPR1995",
}