@STRING{ann = {Annual}}
@STRING{approx = {International Workshop on Approximation Algorithms for Combinatorial
	Optimization Problems}}
@STRING{proc = {Proceedings of the}}
@STRING{approx04 = proc # { 7th } # ann # { } # approx}
@STRING{approx09 = proc # { 12th } # ann # { } # approx}
@STRING{ccc = {IEEE Conference on Computational Complexity}}
@STRING{ccc06 = proc # { 21st } # ann # { } # ccc}
@STRING{ccc07 = proc # { 22nd } # ann # { } # ccc}
@STRING{ccc09 = proc # { 24th } # ann # { } # ccc}
@STRING{ccc10 = proc # { 25th } # ann # { } # ccc}
@STRING{ccc11 = proc # { 26th } # ann # { } # ccc}
@STRING{colt = {Conference on Learning Theory}}
@STRING{colt08 = proc # { 21st } # ann # { } # colt}
@STRING{colt09 = proc # { 22nd } # ann # { } # colt}
@STRING{eccc = {Electronic Colloquium on Computational Complexity}}
@STRING{focs = {IEEE Symposium on Foundations of Computer Science}}
@STRING{focs03 = proc # { 44th } # ann # { } # focs}
@STRING{focs05 = proc # { 46th } # ann # { } # focs}
@STRING{focs06 = proc # { 47th } # ann # { } # focs}
@STRING{focs07 = proc # { 48th } # ann # { } # focs}
@STRING{focs08 = proc # { 49th } # ann # { } # focs}
@STRING{focs09 = proc # { 50th } # ann # { } # focs}
@STRING{focs10 = proc # { 51st } # ann # { } # focs}
@STRING{focs11 = proc # { 52nd } # ann # { } # focs}
@STRING{focs85 = proc # { 26th } # ann # { } # focs}
@STRING{focs88 = proc # { 29th } # ann # { } # focs}
@STRING{focs89 = proc # { 30th } # ann # { } # focs}
@STRING{icalp = {International Colloquium on Automata, Languages and Programming}}
@STRING{icalp07 = proc # { 35th } # ann # { } # icalp}
@STRING{icalp09 = proc # { 36th } # ann # { } # icalp}
@STRING{icalp10 = proc # { 37th } # ann # { } # icalp}
@STRING{ics = {Symposium on Innovations in Computer Science}}
@STRING{ics11 = proc # { 2nd } # ann # { } # ics}
@STRING{ipco = {Conference on Integer Programming and Combinatorial Optimization}}
@STRING{ipco02 = proc # { 6th } # ann # { } # ipco}
@STRING{isaac = {International Symposium on Algorithms and Computation}}
@STRING{isaac09 = proc # { 20th } # ann # { } # isaac}
@STRING{latin = {Latin American Informatics Symposium}}
@STRING{latin04 = proc # { 6th } # ann # { } # latin}
@STRING{LCS = {Lecture Notes in Computer Science}}
@STRING{lics = {IEEE Symposium on Logic in Computer Science}}
@STRING{lics10 = proc # { 25th } # ann # { } # lics}
@STRING{random = {International Workshop on Randomized Techniques in Computation}}
@STRING{random01 = proc # { 5th } # ann # { } # random}
@STRING{random08 = proc # { 12th } # ann # { } # random}
@STRING{random09 = proc # { 13th } # ann # { } # random}
@STRING{random10 = proc # { 14th } # ann # { } # random}
@STRING{soda = {ACM-SIAM Symposium on Discrete Algorithms}}
@STRING{soda09 = proc # { 20th } # ann # { } # soda}
@STRING{soda11 = proc # { 22nd } # ann # { } # soda}
@STRING{soda98 = proc # { 9th } # ann # { } # soda}
@STRING{stacs = {Symposium on Theoretical Aspects of Computer Science}}
@STRING{stacs00 = proc # { 17th } # ann # { } # stacs}
@STRING{stoc = {ACM Symposium on Theory of Computing}}
@STRING{stoc02 = proc # { 34th } # ann # { } # stoc}
@STRING{stoc06 = proc # { 38th } # ann # { } # stoc}
@STRING{stoc07 = proc # { 39th } # ann # { } # stoc}
@STRING{stoc08 = proc # { 40th } # ann # { } # stoc}
@STRING{stoc09 = proc # { 41st } # ann # { } # stoc}
@STRING{stoc10 = proc # { 42nd } # ann # { } # stoc}
@STRING{stoc11 = proc # { 43rd } # ann # { } # stoc}
@STRING{stoc78 = proc # { 10th } # ann # { } # stoc}
@STRING{stoc84 = proc # { 16th } # ann # { } # stoc}
@STRING{stoc87 = proc # { 19th } # ann # { } # stoc}
@STRING{stoc89 = proc # { 21st } # ann # { } # stoc}
@STRING{stoc90 = proc # { 22nd } # ann # { } # stoc}
@STRING{stoc93 = proc # { 25th } # ann # { } # stoc}
@STRING{stoc96 = proc # { 28th } # ann # { } # stoc}
@STRING{stoc97 = proc # { 29th } # ann # { } # stoc}
@STRING{stoc98 = proc # { 30th } # ann # { } # stoc}

@BOOK{Chv83,
  title = {Linear Programming},
  publisher = {W. H. Freeman and Company},
  year = {1983},
  author = {Chv\'{a}tal, Va\v{s}ek},
  address = {New York},
}

@ARTICLE{FT87,
   author = {Frank, Andr\'{a}s and Tardos, \'{E}va},
   title = {An application of simultaneous Diophantine approximation in combinatorial optimization},
   journal = {Combinatorica},
   year = {1987},
   volume = {7},
   pages = {49--65},
}

@BOOK{GLS88,
  title = {Geometric Algorithms and Combinatorial Optimization},
  publisher = {Springer},
  year = {1988},
  author = {Gr\"{o}tschel, Martin and  Lov\'{a}sz, L\'{a}sl\'{o} and Schrijver, Alexander},
}


@ARTICLE{GW95,
  author = {Goemans, Michel and Williamson, David},
  title = {Improved approximation algorithms for maximum cut and satisfiability
	problems using semidefinite programming},
  journal = {Journal of the ACM},
  year = {1995},
  volume = {42},
  pages = {1115--1145},
}

@inproceedings{Kar84a,
  author = {Karmarkar, Narendra},
  title = {A new polynomial-time algorithm for linear programming},
  booktitle = stoc84,
  year = {1984},
  pages = {302--311},
}

@ARTICLE{Kar84b,
  author = {Karmarkar, Narendra},
  title = {A new polynomial-time algorithm for linear programming},
  journal = {Combinatorica},
  year = {1984},
  volume = {4},
  number = {4},
  pages = {373--395},
}

@INBOOK{Nes00,
  author = {Nesterov, Yurii},
  title = {Global quadratic optimization via conic relaxation},
  booktitle = {Handbook of Semidefinite Programming},
  pages = {363--384},
  publisher = {Kluwer Academic Publishers},
  year = {2000},
}

@article{Tar86,
  title={A strongly polynomial algorithm to solve combinatorial linear programs},
  author={Eva Tardos},
  journal={Operations Research},
  pages={250--256},
  volume={34},
  number={2},
  year={1986},
}

@ARTICLE{YN76,
   author = {Yudin, David and Nemirovski, Arkadi},
   title = {Informational complexity and effective methods of solution of convex extremal problems},
   journal = {Economics and mathematical methods},
   year = {1976},
   volume = {12},
   issue = {1},
   pages = {357-369},
}

@ARTICLE{Lov72,
   author = {Lov\'asz, L\'aszl\'o},
   title = {Normal Hypergraphs and the Perfect Graph Conjecture},
   journal = {Discrete Math.},
   year = {1972},
   volume = {2},
   pages = {253--267},
}

@ARTICLE{CRST06,
   author = {Chudnovsky, Maria and Robertson, Neil and Seymour, Paul and Thomas, Robin},
   title = {The Strong Perfect Graph Theorem},
   journal = {Annals of Mathematics},
   year = {2006},
   volume = {164},
   issue = {1},
   pages = {51--229}
}

@ARTICLE{CCLSV05,
   author = {Chudnovsky, Maria and Cornuejols, Gerard and Liu, Xinming and Seymour, Paul and Vuskovic, Kristina},
   title = {Recognizing Berge Graphs},
   journal = {Combinatorica},
   year = {2005},
   volume = {25},
   pages = {143--186}
}

@ARTICLE{Lov79,
   author = {Lov\'asz, L\'aszl\'o},
   title = {On the Shannnon capacity of a graph},
   journal = {IEEE Transactions on Information Theory},
   year = {1979},
   volume = {25},
   issue = {1},
   pages = {1--7}
}

@ARTICLE{AK98,
   author = {Alon, Noga and Kahale, Nabil},
   title = {Approximating the independence number via the $\vartheta$-function},
   journal = {Mathematical Programming},
   publisher = {Springer Berlin / Heidelberg},
   issn = {0025-5610},
   keyword = {Mathematics and Statistics},
   pages = {253--264},
   volume = {80},
   issue = {3},
   year = {1998}
}

@ARTICLE{Kon81,
   author = {Konyagin, S. V.},
   affiliation = {M. V. Lomonosov Moscow State University USSR},
   title = {Systems of vectors in Euclidean space and an extremal problem for polynomials},
   journal = {Mathematical Notes},
   publisher = {MAIK Nauka/Interperiodica distributed exclusively by Springer Science+Business Media LLC.},
   issn = {0001-4346},
   keyword = {Mathematics and Statistics},
   pages = {33--40},
   volume = {29},
   issue = {1},
   year = {1981}
}

@ARTICLE{Fei97,
   author = {Feige, Uriel},
   affiliation = {Department of Applied Math. and Computer Science The Weizmann Institute 76100 Rehovot Israel},
   title = {Randomized graph products, chromatic numbers, and the Lov\'asz $\vartheta$-function},
   journal = {Combinatorica},
   publisher = {Springer Berlin / Heidelberg},
   issn = {0209-9683},
   keyword = {Mathematics and Statistics},
   pages = {79--90},
   volume = {17},
   issue = {1},
   year = {1997}
}

@ARTICLE{KG98,
  author = {Kleinberg, Jon and Goemans, Michel X.},
  title = {The Lov\'asz Theta Function and a Semidefinite Programming Relaxation of Vertex Cover},
  journal = {SIAM J. Discret. Math.},
  volume = {11},
  issue = {2},
  month = {May},
  year = {1998},
  issn = {0895-4801},
  pages = {196--204},
  numpages = {9},
  publisher = {Society for Industrial and Applied Mathematics},
  address = {Philadelphia, PA, USA},
  keywords = {approximation algorithms, independent sets, semidefinite programming., vertex cover},
}

@ARTICLE{Has99,
  author = {H{\aa}stad, Johan},
  title = {Clique is hard to approximate within a factor of $n^{1-\epsilon}$},
  journal = {Acta. Math.},
  volume = {182},
  year = {1999},
  pages = {105--142}
}

@article{H,
 author = {H{\aa}stad, Johan},
 title = {Some optimal inapproximability results},
 journal = {J. ACM},
 volume = {48},
 issue = {4},
 month = {July},
 year = {2001},
 issn = {0004-5411},
 pages = {798--859},
 numpages = {62},
 url = {http://doi.acm.org/10.1145/502090.502098},
 doi = {http://doi.acm.org/10.1145/502090.502098},
 acmid = {502098},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Inapproximability, NP-hard optimization problems, linear equations, max-sat, probabilistically checkable 
 proofs},
}

@article{GWSAT,
    author = {Michel X. Goemans and David P. Williamson},
    title = {New 3/4-Approximation Algorithms for MAX SAT},
    year = {1994}
}

@inproceedings{LLZ02,
  title={Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems},
  author={Livnat, D. and Lewin, M. and Zwick, U.},
  booktitle={Proc. of 9th IPCO},
  pages={67--82},
  year={2002}
}

@inproceedings{CMM07,
  title={Near-optimal algorithms for maximum constraint satisfaction problems},
  author={Charikar, M. and Makarychev, K. and Makarychev, Y.},
  booktitle={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
  pages={62--68},
  year={2007},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{KZ97,
  title={A 7/8-approximation algorithm for MAX 3SAT?},
  author={Karloff, H. and Zwick, U.},
  booktitle={focs},
  pages={406},
  year={1997},
  organization={Published by the IEEE Computer Society}
}

@inproceedings{Zwi02,
  title={Computer assisted proof of optimal approximability results},
  author={Zwick, U.},
  booktitle={Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
  pages={496--505},
  year={2002},
  organization={Society for Industrial and Applied Mathematics}
}

@article{HZ99,
  title={Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs},
  author={Halperin, E. and Zwick, U.},
  journal={Integer Programming and Combinatorial Optimization},
  pages={202--217},
  year={1999},
  publisher={Springer}
}

@inproceedings{AW00,
  title={Improved approximation algorithms for MAX SAT},
  author={Asano, T. and Williamson, D.P.},
  booktitle={Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms},
  pages={96--105},
  year={2000},
  organization={Society for Industrial and Applied Mathematics}
}

@techreport{AHK05,
    author = {Sanjeev Arora and Elad Hazan and Satyen Kale},
    title = {The multiplicative weights update method: a meta algorithm and applications},
    institution = {Princeton University},
    year = {2005}
}

@inproceedings{LW89,
  author    = {Nick Littlestone and
               Manfred K. Warmuth},
  title     = {The Weighted Majority Algorithm},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {256-261},
}

@article{FS97,
 author = {Freund, Yoav and Schapire, Robert E.},
 title = {A decision-theoretic generalization of on-line learning and an application to boosting},
 journal = {J. Comput. Syst. Sci.},
 volume = {55},
 issue = {1},
 month = {August},
 year = {1997},
 issn = {0022-0000},
 pages = {119--139},
 numpages = {21},
 url = {http://dl.acm.org/citation.cfm?id=261540.261549},
 doi = {10.1006/jcss.1997.1504},
 acmid = {261549},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
} 

@misc{blog-mw-adv,
  author = {Gupta, Anupam},
  title = {Lecture \#17: Multiplicative Weights, discussion},
  type = {Blog},
  number = {November 9},
  year = {2011},
  howpublished = {\url{http://lpsdp.wordpress.com/2011/11/09/lecture-17-multiplicative-weights-discussion/}}
}

%% Math Reviews number: 1251892 (94k:90129)
@article {DP93,
    AUTHOR = {Delorme, C. and Poljak, S.},
     TITLE = {Laplacian eigenvalues and the maximum cut problem},
   JOURNAL = {Math. Programming},
  FJOURNAL = {Mathematical Programming},
    VOLUME = {62},
      YEAR = {1993},
    NUMBER = {3, Ser. A},
     PAGES = {557--574},
      ISSN = {0025-5610},
     CODEN = {MHPGA4},
   MRCLASS = {90C35 (05C50)},
  MRNUMBER = {1251892 (94k:90129)},
MRREVIEWER = {Rainer Burkard},
       DOI = {10.1007/BF01585184},
       URL = {http://dx.doi.org/10.1007/BF01585184},
}

%% Math Reviews number: 1046300 (91b:90161)
@article {MP90,
    AUTHOR = {Mohar, Bojan and Poljak, Svatopluk},
     TITLE = {Eigenvalues and max-cut problem},
   JOURNAL = {Czechoslovak Math. J.},
  FJOURNAL = {Czechoslovak Mathematical Journal},
    VOLUME = {40(115)},
      YEAR = {1990},
    NUMBER = {2},
     PAGES = {343--352},
      ISSN = {0011-4642},
     CODEN = {CZMJAE},
   MRCLASS = {90C27 (05C50 90B10 90C35)},
  MRNUMBER = {1046300 (91b:90161)},
MRREVIEWER = {D. de Werra},
}

@inproceedings {KL96,
    AUTHOR = {Klein, Philip and Lu, Hsueh-I},
     TITLE = {Efficient approximation algorithms for semidefinite programs
              arising from {MAX} {CUT} and {COLORING}},
 BOOKTITLE = {Proceedings of the {T}wenty-eighth {A}nnual {ACM} {S}ymposium
              on the {T}heory of {C}omputing ({P}hiladelphia, {PA}, 1996)},
     PAGES = {338--347},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {1996},
   MRCLASS = {68R10 (68Q20 68Q25)},
  MRNUMBER = {1427530},
       DOI = {10.1145/237814.237980},
       URL = {http://dx.doi.org/10.1145/237814.237980},
}

@article {GK98,
    AUTHOR = {Garg, Naveen and K{\"o}nemann, Jochen},
     TITLE = {Faster and simpler algorithms for multicommodity flow and
              other fractional packing problems},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {37},
      YEAR = {2007},
    NUMBER = {2},
     PAGES = {630--652 (electronic)},
      ISSN = {0097-5397},
   MRCLASS = {90C27 (68Q25 68W25)},
  MRNUMBER = {2318722 (2008f:90085)},
       DOI = {10.1137/S0097539704446232},
       URL = {http://dx.doi.org/10.1137/S0097539704446232},
}

@inproceedings{AK07,
  author    = {Sanjeev Arora and
               Satyen Kale},
  title     = {A combinatorial, primal-dual approach to semidefinite programs},
  booktitle = {STOC},
  year      = {2007},
  pages     = {227-236},
  ee        = {http://doi.acm.org/10.1145/1250790.1250823},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Steurer10,
  author    = {David Steurer},
  title     = {Fast SDP Algorithms for Constraint Satisfaction Problems},
  booktitle = {SODA},
  year      = {2010},
  pages     = {684-697},
  ee        = {http://www.siam.org/proceedings/soda/2010/SODA10_056_steurerd.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}