@article{MR2032567,
    AUTHOR = {Dinur, Irit and Safra, Shmuel},
     TITLE = {On the hardness of approximating label-cover},
   JOURNAL = {Inform. Process. Lett.},
  FJOURNAL = {Information Processing Letters},
    VOLUME = {89},
      YEAR = {2004},
    NUMBER = {5},
     PAGES = {247--254},
      ISSN = {0020-0190},
     CODEN = {IFPLAT},
   MRCLASS = {68Q15 (05C78 68Q17 68Q25)},
  MRNUMBER = {2 032 567},
}

@inproceedings{MR2004a:68163,
    AUTHOR = {Feige, Uriel},
     TITLE = {Approximation thresholds for combinatorial optimization
              problems},
 BOOKTITLE = {Proceedings of the International Congress of Mathematicians,
              Vol. III (Beijing, 2002)},
     PAGES = {649--658},
 PUBLISHER = {Higher Ed. Press},
   ADDRESS = {Beijing},
      YEAR = {2002},
   MRCLASS = {68W25 (68Q17)},
  MRNUMBER = {2004a:68163},
}

@article{MR99k:68076,
    AUTHOR = {Feige, Uriel and Kilian, Joe},
     TITLE = {Zero knowledge and the chromatic number},
      NOTE = {Complexity 96---The Eleventh Annual IEEE Conference on
              Computational Complexity (Philadelphia, PA)},
   JOURNAL = {J. Comput. System Sci.},
  FJOURNAL = {Journal of Computer and System Sciences},
    VOLUME = {57},
      YEAR = {1998},
    NUMBER = {2},
     PAGES = {187--199},
      ISSN = {0022-0000},
     CODEN = {JCSSBM},
   MRCLASS = {68Q25 (05C15 68Q15 68R10)},
  MRNUMBER = {99k:68076},
}

@book{MR2001f:68002,
    AUTHOR = {Ausiello, G. and Crescenzi, P. and Gambosi, G. and Kann, V.
              and Marchetti-Spaccamela, A. and Protasi, M.},
     TITLE = {Complexity and approximation},
      NOTE = {Combinatorial optimization problems and their approximability
              properties,
              With 1 CD-ROM (Windows and UNIX)},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {1999},
     PAGES = {xx+524},
      ISBN = {3-540-65431-3},
   MRCLASS = {68-02 (65Y20 90-01 90C27 90C60)},
  MRNUMBER = {2001f:68002},
MRREVIEWER = {Alexander I. Barvinok},
}

@misc{compendium,
 author = {Pierluigi Crescenzi and  Viggo Kann (eds.)},
 title = {A Compendium of {NP}-optimization Problems},
 note = {http://www.nada.kth.se/%7Eviggo/problemlist/},
}

@article{MR84a:90044,
    AUTHOR = {Gr{\"o}tschel, M. and Lov{\'a}sz, L. and Schrijver, A.},
     TITLE = {The ellipsoid method and its consequences in combinatorial
              optimization},
   JOURNAL = {Combinatorica},
  FJOURNAL = {Combinatorica. An International Journal of the J\'anos Bolyai
              Mathematical Society},
    VOLUME = {1},
      YEAR = {1981},
    NUMBER = {2},
     PAGES = {169--197},
      ISSN = {0209-9683},
     CODEN = {COMBDI},
   MRCLASS = {90C05 (05Cxx)},
  MRNUMBER = {84a:90044},
}

@article{fourier1826a,
    AUTHOR = {Fourier, J. B. J.},
     TITLE = {Solution d'une question particuli\`ere du calcul des 
              in\'egalit\'es},
   JOURNAL = {Nouveau Bulletin des Sciences par la Soci\'et\'e
              philomathique de Paris},
      YEAR = {1826},
     PAGES = {99--100},
}
@article{MR18:417d,
    AUTHOR = {Kuhn, H. W.},
     TITLE = {Solvability and consistency for linear equations and
              inequalities},
   JOURNAL = {Amer. Math. Monthly},
    VOLUME = {63},
      YEAR = {1956},
     PAGES = {217--232},
}

@article{MR95k:90066,
    AUTHOR = {Goemans, Michel X. and Williamson, David P.},
     TITLE = {A general approximation technique for constrained forest
              problems},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {24},
      YEAR = {1995},
    NUMBER = {2},
     PAGES = {296--317},
      ISSN = {0097-5397},
     CODEN = {SMJCAT},
   MRCLASS = {90C27 (68Q25 68R10)},
  MRNUMBER = {95k:90066},
MRREVIEWER = {Olivia M. Carducci},
}

@article {MR96c:68146,
    AUTHOR = {Agrawal, Ajit and Klein, Philip and Ravi, R.},
     TITLE = {When trees collide: an approximation algorithm for the
              generalized {S}teiner problem on networks},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {24},
      YEAR = {1995},
    NUMBER = {3},
     PAGES = {440--456},
      ISSN = {0097-5397},
     CODEN = {SMJCAT},
   MRCLASS = {68R10 (68M10 68Q20)},
  MRNUMBER = {96c:68146},
}

@incollection{goemans-williamson-primal-dual,
   AUTHOR = {Michael X. Goemans and David Williamson},
    TITLE = {The Primal-Dual Method for Approximation Algorithms and its
             Application to Network Design Problems},
BOOKTITLE = {Approximation Algorithms for NP-Hard Problems},
  EDITOR  = {Dorit Hochbaum},
    PAGES = {144--191},
PUBLISHER = {PWS Publishing Company},
     YEAR = {1997},
}

@article{MR84a:90052,
    AUTHOR = {Bar-Yehuda, R. and Even, S.},
     TITLE = {A linear-time approximation algorithm for the weighted vertex
              cover problem},
   JOURNAL = {J. Algorithms},
  FJOURNAL = {Journal of Algorithms},
    VOLUME = {2},
      YEAR = {1981},
    NUMBER = {2},
     PAGES = {198--203},
      ISSN = {0196-6774},
     CODEN = {JOALDV},
   MRCLASS = {90C10 (05C70 52A37 68C25)},
  MRNUMBER = {84a:90052},
MRREVIEWER = {Klaus Lommatzsch},
}

@inproceedings{MR1427527,
    AUTHOR = {Feige, Uriel},
     TITLE = {A threshold of {$\ln n$} for approximating set cover
              (preliminary version)},
 BOOKTITLE = {Proceedings of the Twenty-eighth Annual ACM Symposium on the
              Theory of Computing (Philadelphia, PA, 1996)},
     PAGES = {314--318},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {1996},
   MRCLASS = {68Q25 (68Q15)},
  MRNUMBER = {1 427 527},
}

@article{MR19:379d,
    AUTHOR = {Ryser, H. J.},
     TITLE = {Combinatorial properties of matrices of zeros and ones},
   JOURNAL = {Canad. J. Math.},
    VOLUME = {9},
      YEAR = {1957},
     PAGES = {371--377},
   MRCLASS = {05.0X},
  MRNUMBER = {19,379d},
MRREVIEWER = {Marshall Hall, Jr.},
}

@article{MR18:267a,
    AUTHOR = {Orden, Alex},
     TITLE = {The transhipment problem},
   JOURNAL = {Management Sci.},
    VOLUME = {2},
      YEAR = {1956},
     PAGES = {276--285},
   MRCLASS = {90.0X},
  MRNUMBER = {18,267a},
MRREVIEWER = {K. J. Arrow},
}

@incollection{MR15:48b,
    AUTHOR = {Dantzig, George B.},
     TITLE = {Application of the simplex method to a transportation problem},
 BOOKTITLE = {Activity Analysis of Production and Allocation},
    SERIES = {Cowles Commission Monograph No. 13},
     PAGES = {359--373},
 PUBLISHER = {John Wiley \& Sons Inc.},
   ADDRESS = {New York, N. Y.},
      YEAR = {1951},
   MRCLASS = {90.0X},
  MRNUMBER = {15,48b},
MRREVIEWER = {H. W. Kuhn},
}

@article{MR19:1024a,
    AUTHOR = {Gale, David},
     TITLE = {A theorem on flows in networks},
   JOURNAL = {Pacific J. Math.},
    VOLUME = {7},
      YEAR = {1957},
     PAGES = {1073--1082},
   MRCLASS = {90.0X},
  MRNUMBER = {19,1024a},
MRREVIEWER = {P. Wolfe},
}

@article{MR57:2505,
    AUTHOR = {Cunningham, W. H.},
     TITLE = {A network simplex method},
   JOURNAL = {Math. Programming},
    VOLUME = {11},
      YEAR = {1976},
    NUMBER = {2},
     PAGES = {105--116},
   MRCLASS = {90B10 (90C35)},
  MRNUMBER = {57 \#2505},
MRREVIEWER = {Der-San Chen},
}

@article{MR91g:68069,
    AUTHOR = {Alon, Noga},
     TITLE = {Generating pseudo-random permutations and maximum flow
              algorithms},
   JOURNAL = {Inform. Process. Lett.},
  FJOURNAL = {Information Processing Letters},
    VOLUME = {35},
      YEAR = {1990},
    NUMBER = {4},
     PAGES = {201--204},
      ISSN = {0020-0190},
     CODEN = {IFPLAT},
   MRCLASS = {68Q25 (05A05 68R05)},
  MRNUMBER = {91g:68069},
}

@incollection{MR1076825,
    AUTHOR = {Cheriyan, Joseph and Hagerup, Torben and Mehlhorn, Kurt},
     TITLE = {Can a maximum flow be computed in {$o(nm)$} time?},
 BOOKTITLE = {Automata, languages and programming (Coventry, 1990)},
    SERIES = {Lecture Notes in Comput. Sci.},
    VOLUME = {443},
     PAGES = {235--248},
 PUBLISHER = {Springer},
   ADDRESS = {New York},
      YEAR = {1990},
   MRCLASS = {68Q25 (90B10)},
  MRNUMBER = {1 076 825},
}

@article{MR92e:68063,
    AUTHOR = {Ahuja, Ravindra K. and Mehlhorn, Kurt and Orlin, James B. and
              Tarjan, Robert E.},
     TITLE = {Faster algorithms for the shortest path problem},
   JOURNAL = {J. Assoc. Comput. Mach.},
  FJOURNAL = {Journal of the Association for Computing Machinery},
    VOLUME = {37},
      YEAR = {1990},
    NUMBER = {2},
     PAGES = {213--223},
      ISSN = {0004-5411},
     CODEN = {JACOAH},
   MRCLASS = {68Q25 (05C35 68R10 90B10)},
  MRNUMBER = {92e:68063},
}

@article{MR91d:68046,
    AUTHOR = {Ahuja, Ravindra K. and Orlin, James B. and Tarjan, Robert E.},
     TITLE = {Improved time bounds for the maximum flow problem},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {18},
      YEAR = {1989},
    NUMBER = {5},
     PAGES = {939--954},
      ISSN = {0097-5397},
     CODEN = {SMJCAT},
   MRCLASS = {68Q25 (90B10)},
  MRNUMBER = {91d:68046},
}

@incollection{MR92i:90043,
    AUTHOR = {Goldberg, Andrew V. and Tardos, {\'E}va and Tarjan, Robert E.},
     TITLE = {Network flow algorithms},
 BOOKTITLE = {Paths, flows, and VLSI-layout (Bonn, 1988)},
    SERIES = {Algorithms Combin.},
    VOLUME = {9},
     PAGES = {101--164},
 PUBLISHER = {Springer},
   ADDRESS = {Berlin},
      YEAR = {1990},
   MRCLASS = {90B10 (68Q25 68R10)},
  MRNUMBER = {92i:90043},
MRREVIEWER = {Ondrej S{\'y}kora},
}

@article{MR92c:90050,
    AUTHOR = {Goldberg, Andrew V. and Tarjan, Robert E.},
     TITLE = {A new approach to the maximum-flow problem},
   JOURNAL = {J. Assoc. Comput. Mach.},
  FJOURNAL = {Journal of the Association for Computing Machinery},
    VOLUME = {35},
      YEAR = {1988},
    NUMBER = {4},
     PAGES = {921--940},
      ISSN = {0004-5411},
     CODEN = {JACOAH},
   MRCLASS = {90B10 (68Q25)},
  MRNUMBER = {92c:90050},
MRREVIEWER = {Robert E. Beck},
}
@article {MR91m:90058,
    AUTHOR = {Goldberg, Andrew V. and Tarjan, Robert E.},
     TITLE = {Finding minimum-cost circulations by canceling negative
              cycles},
   JOURNAL = {J. Assoc. Comput. Mach.},
  FJOURNAL = {Journal of the Association for Computing Machinery},
    VOLUME = {36},
      YEAR = {1989},
    NUMBER = {4},
     PAGES = {873--886},
      ISSN = {0004-5411},
     CODEN = {JACOAH},
   MRCLASS = {90B10},
  MRNUMBER = {91m:90058},
MRREVIEWER = {Claude Benzaken},
}
@article {MR91f:68085,
    AUTHOR = {Goldberg, Andrew V. and Tarjan, Robert E.},
     TITLE = {A parallel algorithm for finding a blocking flow in an acyclic
              network},
   JOURNAL = {Inform. Process. Lett.},
  FJOURNAL = {Information Processing Letters},
    VOLUME = {31},
      YEAR = {1989},
    NUMBER = {5},
     PAGES = {265--271},
      ISSN = {0020-0190},
     CODEN = {IFPLAT},
   MRCLASS = {68Q25 (68Q22 68R10 90B10)},
  MRNUMBER = {91f:68085},
}
@article {MR91d:90038,
    AUTHOR = {Goldberg, Andrew V. and Tarjan, Robert E.},
     TITLE = {Finding minimum-cost circulations by successive approximation},
   JOURNAL = {Math. Oper. Res.},
  FJOURNAL = {Mathematics of Operations Research},
    VOLUME = {15},
      YEAR = {1990},
    NUMBER = {3},
     PAGES = {430--466},
      ISSN = {0364-765X},
   MRCLASS = {90B10},
  MRNUMBER = {91d:90038},
}

@TechReport{goldberg1985,
  author =       {Andrew V. Goldberg},
  title =        {A new max-flow algorithm},
  institution =  {Laboratory for Computer Science, MIT},
  number =       {MIT/LCS/TM-291},
  address =      {Cambridge},
  year =         {1985},
}

@article{MR44:5178,
    AUTHOR = {Dinic, E. A.},
     TITLE = {An algorithm for the solution of the problem of maximal flow
              in a network with power estimation},
   JOURNAL = {Dokl. Akad. Nauk SSSR},
    VOLUME = {194},
      YEAR = {1970},
     PAGES = {754--757},
   MRCLASS = {94.30},
  MRNUMBER = {44 \#5178},
MRREVIEWER = {P. Vondr{\'a}{\v{c}}ek},
}

@article{MR49:8619,
    AUTHOR = {Karzanov, A. V.},
     TITLE = {The problem of finding the maximal flow in a network by the
              method of preflows},
   JOURNAL = {Dokl. Akad. Nauk SSSR},
    VOLUME = {215},
      YEAR = {1974},
     PAGES = {49--52},
   MRCLASS = {90B10},
  MRNUMBER = {49 \#8619},
MRREVIEWER = {M. Manas},
}

@incollection{MR42:1583,
    AUTHOR = {Edmonds, Jack and Karp, Richard M.},
     TITLE = {Theoretical improvements in algorithmic efficiency for network
              flow problems},
 BOOKTITLE = {Combinatorial Structures and their Applications (Proc. Calgary
              Internat. Conf., Calgary, Alta., 1969)},
     PAGES = {93--96},
 PUBLISHER = {Gordon and Breach},
   ADDRESS = {New York},
      YEAR = {1970},
   MRCLASS = {94.30},
  MRNUMBER = {42 \#1583},
MRREVIEWER = {D. R. Fulkerson},
}

@incollection{MR19:719c,
    AUTHOR = {Dantzig, G. B. and Ford, Jr., L. R. and Fulkerson, D. R.},
     TITLE = {A primal-dual algorithm for linear programs},
 BOOKTITLE = {Linear inequalities and related systems},
    SERIES = {Annals of Mathematics Studies, no. 38},
     PAGES = {171--181},
 PUBLISHER = {Princeton University Press},
   ADDRESS = {Princeton, N. J.},
      YEAR = {1956},
   MRCLASS = {90.0X},
  MRNUMBER = {19,719c},
MRREVIEWER = {P. S. Dwyer},
}

@article{MR17:759d,
    AUTHOR = {Kuhn, H. W.},
     TITLE = {The {H}ungarian method for the assignment problem},
   JOURNAL = {Naval Res. Logist. Quart.},
    VOLUME = {2},
      YEAR = {1955},
     PAGES = {83--97},
   MRCLASS = {90.0X},
  MRNUMBER = {17,759d},
MRREVIEWER = {D. Gale},
}

@article{kotzig-1956,
    AUTHOR = {A. Kotzig},
     TITLE = {S\'uvislost' a Pravidelin\'a S\'uvislost'
              Kone\v{c}n\'ych Grafov},
   JOURNAL = {Bratislava: Vysok\'a \v{S}kola Ekonomick\'a},
      YEAR = {1956},
}

@article{elias-1956,
    AUTHOR = {P. Elias and A. Feinstein and C. E. Shannon},
     TITLE = {Note on maximal flow through a network},
   JOURNAL = {IRE Transactions on Information Theory IT-2},
      YEAR = {1956},
     PAGES = {117--199},
}

@article{MR18:56h,
    AUTHOR = {Ford, Jr., L. R. and Fulkerson, D. R.},
     TITLE = {Maximal flow through a network},
   JOURNAL = {Canad. J. Math.},
    VOLUME = {8},
      YEAR = {1956},
     PAGES = {399--404},
}

@article{MR87i:90162,
    AUTHOR = {Hall, Nicholas G. and Hochbaum, Dorit S.},
     TITLE = {A fast approximation algorithm for the multicovering problem},
   JOURNAL = {Discrete Appl. Math.},
  FJOURNAL = {Discrete Applied Mathematics. Combinatorial Algorithms,
              Optimization and Computer Science},
    VOLUME = {15},
      YEAR = {1986},
    NUMBER = {1},
     PAGES = {35--40},
      ISSN = {0166-218X},
     CODEN = {DAMADU},
   MRCLASS = {90C10},
  MRNUMBER = {87i:90162},
}

@article{MR56:7317,
    AUTHOR = {Johnson, David S.},
     TITLE = {Approximation algorithms for combinatorial problems},
      NOTE = {Fifth Annual ACM Symposium on the Theory of Computing (Austin,
              Tex., 1973)},
   JOURNAL = {J. Comput. System Sci.},
    VOLUME = {9},
      YEAR = {1974},
     PAGES = {256--278},
   MRCLASS = {68A20 (65K05)},
  MRNUMBER = {56 \#7317},
MRREVIEWER = {A. V. Anisimov},
}

@article{MR52:5452,
    AUTHOR = {Lov{\'a}sz, L.},
     TITLE = {On the ratio of optimal integral and fractional covers},
   JOURNAL = {Discrete Math.},
    VOLUME = {13},
      YEAR = {1975},
    NUMBER = {4},
     PAGES = {383--390},
   MRCLASS = {05B40},
  MRNUMBER = {52 \#5452},
MRREVIEWER = {Torrence D. Parsons},
}

@article{MR83g:90089,
    AUTHOR = {Hochbaum, Dorit S.},
     TITLE = {Approximation algorithms for the set covering and vertex cover
              problems},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {11},
      YEAR = {1982},
    NUMBER = {3},
     PAGES = {555--556},
      ISSN = {0097-5397},
     CODEN = {SMJCAT},
   MRCLASS = {90C10 (65K05)},
  MRNUMBER = {83g:90089},
}

@inProceedings{garey-graham-ullman,
    AUTHOR = {M. R. Garey and R. L. Graham and J. D. Ullman},
     TITLE = {Worst Case Analysis of Memory Allocation Algorithms},
 BOOKTITLE = {Proceedings of the Fourth Annual ACM Symposium on 
              Theory of Computing (STOC)},
     PAGES = {143--150},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {1972},
}

@incollection{MR54:9659,
    AUTHOR = {Garey, M. R. and Graham, R. L. and Ullman, J. D.},
     TITLE = {An analysis of some packing algorithms},
 BOOKTITLE = {Combinatorial algorithms (Courant Comput. Sci. Sympos., No. 9,
              1972)},
     PAGES = {39--47},
 PUBLISHER = {Algorithmics Press, New York},
      YEAR = {1973},
}

@book{MR2002h:68001,
    AUTHOR = {Vazirani, Vijay V.},
     TITLE = {Approximation algorithms},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {2001},
     PAGES = {xx+378},
      ISBN = {3-540-65367-8},
   MRCLASS = {68-02 (68Q17 68Q25 68W25 90Cxx)},
  MRNUMBER = {2002h:68001},
MRREVIEWER = {Mark R. Jerrum},
}

@book{MR99f:90002,
    AUTHOR = {Wolsey, Laurence A.},
     TITLE = {Integer programming},
    SERIES = {Wiley-Interscience Series in Discrete Mathematics and
              Optimization},
      NOTE = {A Wiley-Interscience Publication},
 PUBLISHER = {John Wiley \& Sons Inc.},
   ADDRESS = {New York},
      YEAR = {1998},
     PAGES = {xx+264},
      ISBN = {0-471-28366-5},
   MRCLASS = {90-01 (90C10)},
  MRNUMBER = {99f:90002},
MRREVIEWER = {Anton Volgenant},
}

@inProceedings{spielman-teng-2001,
    AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
     TITLE = {Smoothed Analysis of Algorithms: Why the Simplex 
              Algorithm Usually Takes Polynomial Time},
 BOOKTITLE = {Proceedings of the Thirty-Third Annual
              ACM Symposium on Theory of Computing
              (STOC'2001, Heraklion, Crete, Greece)},
     PAGES = {296--305},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {2001}, 
}             

@article{MR92h:52017,
    AUTHOR = {Kalai, Gil and Kleitman, Daniel J.},
     TITLE = {A quasi-polynomial bound for the diameter of graphs of
              polyhedra},
   JOURNAL = {Bull. Amer. Math. Soc. (N.S.)},
  FJOURNAL = {American Mathematical Society. Bulletin. New Series},
    VOLUME = {26},
      YEAR = {1992},
    NUMBER = {2},
     PAGES = {315--316},
      ISSN = {0273-0979},
     CODEN = {BAMOAD},
   MRCLASS = {52B55},
  MRNUMBER = {92h:52017},
MRREVIEWER = {W. J. Firey},
}

@article{MR51:7611,
    AUTHOR = {Jeroslow, R. G.},
     TITLE = {The simplex algorithm with the pivot rule of maximizing
              criterion improvement},
   JOURNAL = {Discrete Math.},
    VOLUME = {4},
      YEAR = {1973},
     PAGES = {367--377},
   MRCLASS = {90C05},
  MRNUMBER = {51 \#7611},
MRREVIEWER = {S. Cruceanu},
}

@article{MR57:5793,
    AUTHOR = {Bland, Robert G.},
     TITLE = {A combinatorial abstraction of linear programming},
   JOURNAL = {J. Combinatorial Theory Ser. B},
    VOLUME = {23},
      YEAR = {1977},
    NUMBER = {1},
     PAGES = {33--57},
   MRCLASS = {05B35 (90C05)},
  MRNUMBER = {57 \#5793},
MRREVIEWER = {Andras Recski},
}

@article{MR56:17791,
    AUTHOR = {Bland, Robert G.},
     TITLE = {New finite pivoting rules for the simplex method},
   JOURNAL = {Math. Oper. Res.},
    VOLUME = {2},
      YEAR = {1977},
    NUMBER = {2},
     PAGES = {103--107},
   MRCLASS = {90C05},
  MRNUMBER = {56 \#17791},
MRREVIEWER = {Jacques Dubois},
}

@article{MR16:1054i,
    AUTHOR = {Dantzig, George B. and Orden, Alex and Wolfe, Philip},
     TITLE = {The generalized simplex method for minimizing a linear form
              under linear inequality restraints},
   JOURNAL = {Pacific J. Math.},
    VOLUME = {5},
      YEAR = {1955},
     PAGES = {183--195},
   MRCLASS = {65.0X},
  MRNUMBER = {16,1054i},
MRREVIEWER = {A. J. Hoffman},
}

@article{MR15:48d,
    AUTHOR = {Charnes, A.},
     TITLE = {Optimality and degeneracy in linear programming},
   JOURNAL = {Econometrica},
    VOLUME = {20},
      YEAR = {1952},
     PAGES = {160--170},
   MRCLASS = {90.0X},
  MRNUMBER = {15,48d},
MRREVIEWER = {D. Gale},
}

@inproceedings{MR15:354b,
    AUTHOR = {Charnes, A. and Lemke, C. E.},
     TITLE = {Computational problems of linear programming},
 BOOKTITLE = {Proceedings of the Association for Computing Machinery,
              Pittsburgh, 1952},
     PAGES = {97--98},
 PUBLISHER = {Richard Rimbach Associates, Pittsburgh, P. A.},
      YEAR = {1952},
   MRCLASS = {65.0X},
  MRNUMBER = {15,354b},
}

@article{MR18:514e,
    AUTHOR = {Beale, E. M. L.},
     TITLE = {Cycling in the dual simplex algorithm},
   JOURNAL = {Naval Res. Logist. Quart.},
    VOLUME = {2},
      YEAR = {1955},
     PAGES = {269--275 (1956)},
   MRCLASS = {65.3X},
  MRNUMBER = {18,514e},
MRREVIEWER = {A. J. Hoffman},
}

@article{interior,
    AUTHOR = {Forsgren, Anders and Gill, Philip E. and Wright, Margaret H.},
     TITLE = {Interior Methods for Nonlinear Optimization},
   JOURNAL = {{SIAM} Review},
    VOLUME = {44},
      YEAR = {2002},
    NUMBER = {4},
     PAGES = {525--598},
}

@incollection{MR48:10492,
    AUTHOR = {Klee, Victor and Minty, George J.},
     TITLE = {How good is the simplex algorithm?},
 BOOKTITLE = {Inequalities, III (Proc. Third Sympos., Univ. California, Los
              Angeles, Calif., 1969; dedicated to the memory of Theodore S.
              Motzkin)},
     PAGES = {159--175},
 PUBLISHER = {Academic Press},
   ADDRESS = {New York},
      YEAR = {1972},
   MRCLASS = {90C05},
  MRNUMBER = {48 \#10492},
MRREVIEWER = {Robert G. Jeroslow},
}

@article{khachian,
    AUTHOR = {Khachian, L. G.},
     TITLE = {A Polynomial Algorithm for Linear Programming},
   JOURNAL = {Dokl. Akad. Nauk SSSR},
  FJOURNAL = {Journal of Optimization Theory and Applications},
    VOLUME = {244},
      YEAR = {1979},
    NUMBER = {5},
     PAGES = {1093--1096},
      NOTE = {English translation in Soviet Math. Dokl. 20, 191-194, 1979},
}

@article{MR86i:90072,
    AUTHOR = {Karmarkar, N.},
     TITLE = {A new polynomial-time algorithm for linear programming},
   JOURNAL = {Combinatorica},
  FJOURNAL = {Combinatorica. An International Journal of the J\'anos Bolyai
              Mathematical Society},
    VOLUME = {4},
      YEAR = {1984},
    NUMBER = {4},
     PAGES = {373--395},
      ISSN = {0209-9683},
     CODEN = {COMBDI},
   MRCLASS = {90C05},
  MRNUMBER = {86i:90072},
MRREVIEWER = {K. G. Murty},
}

@article{MR93b:90045,
    AUTHOR = {Ye, Y. Y.},
     TITLE = {Extensions of the potential reduction algorithm for linear
              programming},
   JOURNAL = {J. Optim. Theory Appl.},
  FJOURNAL = {Journal of Optimization Theory and Applications},
    VOLUME = {72},
      YEAR = {1992},
    NUMBER = {3},
     PAGES = {487--498},
      ISSN = {0022-3239},
     CODEN = {JOTABN},
   MRCLASS = {90C05 (90D05)},
  MRNUMBER = {93b:90045},
MRREVIEWER = {Juan Garc{\'{\i}}a Laguna},
}

@article{MR92h:90081,
    AUTHOR = {Ye, Yinyu},
     TITLE = {An {$O(n\sp 3L)$} potential reduction algorithm for linear
              programming},
   JOURNAL = {Math. Programming},
  FJOURNAL = {Mathematical Programming},
    VOLUME = {50},
      YEAR = {1991},
    NUMBER = {2, (Ser. A)},
     PAGES = {239--258},
      ISSN = {0025-5610},
     CODEN = {MHPGA4},
   MRCLASS = {90C05 (65K05)},
  MRNUMBER = {92h:90081},
MRREVIEWER = {Adam Korytowski},
}

@incollection{MR15:47k,
    AUTHOR = {Dantzig, George B.},
     TITLE = {Maximization of a linear function of variables subject to
              linear inequalities},
 BOOKTITLE = {Activity Analysis of Production and Allocation},
    SERIES = {Cowles Commission Monograph No. 13},
     PAGES = {339--347},
 PUBLISHER = {John Wiley \& Sons Inc.},
   ADDRESS = {New York, N. Y.},
      YEAR = {1951},
   MRCLASS = {90.0X},
  MRNUMBER = {15,47k},
MRREVIEWER = {H. W. Kuhn},
}

@article{MR2000f:68049,
    AUTHOR = {Feige, Uriel},
     TITLE = {A threshold of {$\ln n$} for approximating set cover},
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {45},
      YEAR = {1998},
    NUMBER = {4},
     PAGES = {634--652},
      ISSN = {0004-5411},
   MRCLASS = {68Q17 (05C70)},
  MRNUMBER = {2000f:68049},
MRREVIEWER = {Uwe Sch{\"o}ning},
}

@incollection{MR1715654,
    AUTHOR = {Raz, Ran and Safra, Shmuel},
     TITLE = {A sub-constant error-probability low-degree test, and a
              sub-constant error-probability {PCP} characterization of {NP}},
 BOOKTITLE = {STOC '97 (El Paso, TX)},
     PAGES = {475--484 (electronic)},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {1999},
   MRCLASS = {68Q15},
  MRNUMBER = {1 715 654},
}

@inproceedings{MR1755538,
    AUTHOR = {Robins, Gabriel and Zelikovsky, Alexander},
     TITLE = {Improved {S}teiner tree approximation in graphs},
 BOOKTITLE = {Proceedings of the Eleventh Annual ACM-SIAM Symposium on
              Discrete Algorithms (San Francisco, CA, 2000)},
     PAGES = {770--779},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {2000},
   MRCLASS = {68R10 (68W25)},
  MRNUMBER = {1 755 538},
}

@incollection{MR98h:68105,
    AUTHOR = {Alimonti, Paola and Kann, Viggo},
     TITLE = {Hardness of approximating problems on cubic graphs},
 BOOKTITLE = {Algorithms and complexity (Rome, 1997)},
    SERIES = {Lecture Notes in Comput. Sci.},
    VOLUME = {1203},
     PAGES = {288--298},
 PUBLISHER = {Springer},
   ADDRESS = {Berlin},
      YEAR = {1997},
   MRCLASS = {68Q25 (05C85 68R10)},
  MRNUMBER = {98h:68105},
}

@article{MR2000c:68107,
    AUTHOR = {Guha, Sudipto and Khuller, Samir},
     TITLE = {Improved methods for approximating node weighted {S}teiner
              trees and connected dominating sets},
   JOURNAL = {Inform. and Comput.},
  FJOURNAL = {Information and Computation},
    VOLUME = {150},
      YEAR = {1999},
    NUMBER = {1},
     PAGES = {57--74},
      ISSN = {0890-5401},
   MRCLASS = {68R10 (68W25 68W40)},
  MRNUMBER = {2000c:68107},
}

@article{MR98m:68207,
    AUTHOR = {Guha, S. and Khuller, S.},
     TITLE = {Approximation algorithms for connected dominating sets},
   JOURNAL = {Algorithmica},
  FJOURNAL = {Algorithmica. An International Journal in Computer Science},
    VOLUME = {20},
      YEAR = {1998},
    NUMBER = {4},
     PAGES = {374--387},
      ISSN = {0178-4617},
     CODEN = {ALGOEJ},
   MRCLASS = {68R10 (68Q25)},
  MRNUMBER = {98m:68207},
}

@incollection{MR98g:68125,
    AUTHOR = {Guha, Sudipto and Khuller, Samir},
     TITLE = {Approximation algorithms for connected dominating sets},
 BOOKTITLE = {Algorithms---ESA '96 (Barcelona)},
    SERIES = {Lecture Notes in Comput. Sci.},
    VOLUME = {1136},
     PAGES = {179--193},
 PUBLISHER = {Springer},
   ADDRESS = {Berlin},
      YEAR = {1996},
   MRCLASS = {68R10 (05C85 68Q25)},
  MRNUMBER = {98g:68125},
}

@article{MR80g:90082,
    AUTHOR = {Chv{\'a}tal, V.},
     TITLE = {A greedy heuristic for the set-covering problem},
   JOURNAL = {Math. Oper. Res.},
  FJOURNAL = {Mathematics of Operations Research},
    VOLUME = {4},
      YEAR = {1979},
    NUMBER = {3},
     PAGES = {233--235},
      ISSN = {0364-765X},
   MRCLASS = {90C10},
  MRNUMBER = {80g:90082},
MRREVIEWER = {Leon Cooper},
}