[1]   Noga Alon and Joel Spencer: The Probabilistic Method. Wiley-Interscience, 2008.

[2]   Esther M. Arkin and Refael Hassin: On local search for weighted k-set packing. Math. Oper. Res., 23(3):640–648, 1998. Preliminary version in ESA’97. [doi:10.1287/moor.23.3.640]

[3]   Per Austrin, Subhash Khot, and Muli Safra: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(3):27–43, 2011. Preliminary version in CCC’09. [doi:10.4086/toc.2011.v007a003]

[4]   Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan: On k-column sparse packing programs. In Proc. 14th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’10), pp. 369–382, 2010. [doi:10.1007/978-3-642-13036-6_28]

[5]   József Beck and Tibor Fiala: “Integer-making” theorems. Discrete Appl. Math., 3(1):1–8, 1981. [doi:10.1016/0166-218X(81)90022-6]

[6]   Piotr Berman: A d∕2 approximation for maximum weight independent set in d-claw free graphs. Nord. J. Comput., 7(3):178–184, 2000. Preliminary version in SWAT’00.

[7]   Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740–1766, 2011. Combines results from IPCO’07 and STOC’08. [doi:10.1137/080733991]

[8]   Barun Chandra and Magnús M. Halldórsson: Greedy local improvement and weighted set packing approximation. J. Algorithms, 39(2):223–240, 2001. Preliminary version in SODA’99. [doi:10.1006/jagm.2000.1155]

[9]   Chandra Chekuri, Alina Ene, and Nitish Korula: Personal communication, 2009.

[10]   Funda Ergün, Rakesh K. Sinha, and Lisa Zhang: QoS routing with performance-dependent costs. In 19th Ann. Joint Conf. IEEE Computer and Communications Societies (INFOCOM’00), pp. 137–146, 2000. [doi:10.1109/INFCOM.2000.832182]

[11]   Uriel Feige: On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122–142, 2009. Preliminary version in STOC’06. [doi:10.1137/070680977]

[12]   Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz, and Justin Ward: Improved approximations for k-exchange systems - (extended abstract). In Proc. 19th Ann. European Symp. on Algorithms (ESA’11), pp. 784–798, 2011. [doi:10.1007/978-3-642-23719-5_66]

[13]   M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey: An analysis of approximations for maximizing submodular set functions II. Math. Prog. Study, 8:73–87, 1978. [doi:10.1007/BFb0121195]

[14]   Eran Halperin: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput., 31(5):1608–1623, 2002. Preliminary version in SODA’00. [doi:10.1137/S0097539700381097]

[15]   Elad Hazan, Shmuel Safra, and Oded Schwartz: On the complexity of approximating k-set packing. Comput. Complexity, 15(1):20–39, 2006. Preliminary version in APPROX’03. [doi:10.1007/s00037-006-0205-6]

[16]   Cor A. J. Hurkens and Alexander Schrijver: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math., 2(1):68–72, 1989. [doi:10.1137/0402008]

[17]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[18]    Stavros G. Kolliopoulos and Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Program., 99(1):63–87, 2004. Preliminary version in IPCO’98. [doi:10.1007/s10107-002-0370-6]

[19]   Jochen Könemann and R. Ravi: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J. Comput., 31(6):1783–1793, 2002. Preliminary version in STOC’00. [doi:10.1137/S009753970036917X]

[20]   Ariel Kulik, Hadas Shachnai, and Tami Tamir: Maximizing submodular set functions subject to multiple linear constraints. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 545–554. ACM Press, 2009. [ACM:1496770.1496830]

[21]   Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math., 23(4):2053–2078, 2010. Preliminary version in STOC’09. [doi:10.1137/090750020]

[22]   Michael Luby and Noam Nisan: A parallel approximation algorithm for positive linear programming. In Proc. 25th STOC, pp. 448–457. ACM Press, 1993. [doi:10.1145/167088.167211]

[23]   Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.

[24]   David Pritchard: Approximability of sparse integer programs. In Proc. 17th Ann. European Symp. on Algorithms (ESA’09), pp. 83–94. Springer, 2009. [doi:10.1007/978-3-642-04128-0_8]

[25]   David Pritchard and Deeparnab Chakrabarty: Approximability of sparse integer programs. Algorithmica, 61(1):75–93, 2011. [doi:10.1007/s00453-010-9431-z]

[26]   Prabhakar Raghavan: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. System Sci., 37(2):130–143, 1988. Preliminary version in FOCS’86. [doi:10.1016/0022-0000(88)90003-7]

[27]   F. Bruce Shepherd and Adrian Vetta: The demand-matching problem. Math. Oper. Res., 32(3):563–578, 2007. Preliminary version in IPCO’02. [doi:10.1287/moor.1070.0254]

[28]   David B. Shmoys and Éva Tardos: An approximation algorithm for the generalized assignment problem. Math. Program., 62(1-3):461–474, 1993. [doi:10.1007/BF01585178]

[29]   Aravind Srinivasan: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput., 29(2):648–670, 1999. Preliminary version in STOC’95. [doi:10.1137/S0097539796314240]

[30]   Aravind Srinivasan: New approaches to covering and packing problems. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 567–576. ACM Press, 2001. [ACM:365411.365535]

[31]   Jan Vondrák: Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th STOC, pp. 67–74. ACM Press, 2008. [doi:10.1145/1374376.1374389]

[32]   Justin Ward: A (k + 3)∕2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. In Proc. 29th Symp. Theoretical Aspects of Comp. Sci. (STACS’12), pp. 42–53. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. [doi:10.4230/LIPIcs.STACS.2012.42]

[33]   David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103–128, 2007. Preliminary version in STOC’06. [doi:10.4086/toc.2007.v003a006]