{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:33:24Z","timestamp":1762101204091},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_66","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"784-798","source":"Crossref","is-referenced-by-count":16,"title":["Improved Approximations for k-Exchange Systems"],"prefix":"10.1007","author":[{"given":"Moran","family":"Feldman","sequence":"first","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[]},{"given":"Justin","family":"Ward","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"66_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(87)90178-5","volume":"24","author":"R.P. Anstee","year":"1987","unstructured":"Anstee, R.P.: A polynomial algorithm for b-matchings: An alternative approach. Information Processing Letters\u00a024(3), 153\u2013157 (1987)","journal-title":"Information Processing Letters"},{"key":"66_CR2","first-page":"178","volume":"7","author":"P. Berman","year":"2000","unstructured":"Berman, P.: A d\/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. of Computing\u00a07, 178\u2013184 (2000)","journal-title":"Nordic J. of Computing"},{"issue":"02","key":"66_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"R.A. Brualdi","year":"1969","unstructured":"Brualdi, R.A.: Comments on bases in dependence structures. Bull. of the Australian Math. Soc.\u00a01(02), 161\u2013167 (1969)","journal-title":"Bull. of the Australian Math. Soc."},{"issue":"3","key":"66_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0021-9800(70)80084-9","volume":"8","author":"R.A. Brualdi","year":"1970","unstructured":"Brualdi, R.A.: Common transversals and strong exchange systems. J. of Combinatorial Theory\u00a08(3), 307\u2013329 (1970)","journal-title":"J. of Combinatorial Theory"},{"key":"66_CR5","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1090\/S0002-9939-1971-0289335-5","volume":"29","author":"R.A. Brualdi","year":"1971","unstructured":"Brualdi, R.A.: Induced matroids. Proc. of the American Math. Soc.\u00a029, 213\u2013221 (1971)","journal-title":"Proc. of the American Math. Soc."},{"issue":"3","key":"66_CR6","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/S0021-9800(68)80071-7","volume":"5","author":"R.A. Brualdi","year":"1968","unstructured":"Brualdi, R.A., Scrimger, E.B.: Exchange systems, matchings, and transversals. J. of Combinatorial Theory\u00a05(3), 244\u2013257 (1968)","journal-title":"J. of Combinatorial Theory"},{"key":"66_CR7","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. To appear in SIAM Journal on Computing, Special Issue for STOC 2008 (2008)"},{"key":"66_CR8","unstructured":"Chandra, B., Halld\u00f3rsson, M.: Greedy local improvement and weighted set packing approximation. In: SODA, pp. 169\u2013176 (1999)"},{"key":"66_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"issue":"3","key":"66_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M. Conforti","year":"1984","unstructured":"Conforti, M., Cornu\u00e8jols, G.: Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Disc. Appl. Math.\u00a07(3), 251\u2013274 (1984)","journal-title":"Disc. Appl. Math."},{"key":"66_CR11","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume-title":"Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium","author":"J. Edmonds","year":"1979","unstructured":"Edmonds, J.: Matroid intersection. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Annals of Discrete Mathematics, vol.\u00a04, pp. 39\u201349. Elsevier, Amsterdam (1979)"},{"key":"66_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. In: FOCS, pp. 461\u2013471 (2007)","DOI":"10.1109\/FOCS.2007.4389516"},{"key":"66_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-642-22006-7_29","volume-title":"Automata, Languages and Programming","author":"M. Feldman","year":"2011","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 342\u2013353. Springer, Heidelberg (2011)"},{"key":"66_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. To appear in FOCS 2011 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"66_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M. Fisher","year":"1978","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for maximizing submodular set functions - ii. Math. Prog. Study\u00a08, 73\u201387 (1978)","journal-title":"Math. Prog. Study"},{"key":"66_CR16","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Vondr\u00e1k, J.: Submodular maximization by simulated annealing. In: SODA, pp. 1098\u20131116 (2011)","DOI":"10.1137\/1.9781611973082.83"},{"key":"66_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-17572-5_20","volume-title":"Internet and Network Economics","author":"A. Gupta","year":"2010","unstructured":"Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: Saberi, A. (ed.) WINE 2010. LNCS, vol.\u00a06484, pp. 246\u2013257. Springer, Heidelberg (2010)"},{"issue":"1","key":"66_CR18","first-page":"219","volume":"22","author":"D. Hausmann","year":"1978","unstructured":"Hausmann, D., Korte, B.: K-greedy algorithms for independence systems. Oper. Res. Ser. A-B\u00a022(1), 219\u2013228 (1978)","journal-title":"Oper. Res. Ser. A-B"},{"key":"66_CR19","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/BFb0120891","volume":"12","author":"D. Hausmann","year":"1980","unstructured":"Hausmann, D., Korte, B., Jenkyns, T.: Worst case analysis of greedy type algorithms for independence systems. Math. Prog. Study\u00a012, 120\u2013131 (1980)","journal-title":"Math. Prog. Study"},{"key":"66_CR20","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex.\u00a015, 20\u201339 (2006)","journal-title":"Comput. Complex."},{"issue":"1","key":"66_CR21","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: 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. Disc. Math.\u00a02(1), 68\u201372 (1989)","journal-title":"SIAM J. Disc. Math."},{"key":"66_CR22","first-page":"341","volume":"17","author":"T. Jenkyns","year":"1976","unstructured":"Jenkyns, T.: The efficacy of the greedy algorithm. Cong. Num.\u00a017, 341\u2013350 (1976)","journal-title":"Cong. Num."},{"issue":"1","key":"66_CR23","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/0211014","volume":"11","author":"P.M. Jensen","year":"1982","unstructured":"Jensen, P.M., Korte, B.: Complexity of matroid property algorithms. SIAM J. Computing\u00a011(1), 184 (1982)","journal-title":"SIAM J. Computing"},{"key":"66_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-62034-6_49","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"B. Kalyanasundaram","year":"1996","unstructured":"Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 193\u2013199. Springer, Heidelberg (1996)"},{"key":"66_CR25","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B. Korte","year":"1978","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Annals of Discrete Math.\u00a02, 65\u201374 (1978)","journal-title":"Annals of Discrete Math."},{"key":"66_CR26","doi-asserted-by":"crossref","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. To appear in Mathematics of Operations Research (2009)","DOI":"10.1007\/978-3-642-03685-9_19"},{"key":"66_CR27","doi-asserted-by":"crossref","unstructured":"Lee, J., Sviridenko, M., Vondrak, J.: Matroid matching: the power of local search. In: STOC, pp. 369\u2013378 (2010)","DOI":"10.1145\/1806689.1806741"},{"key":"66_CR28","unstructured":"Lov\u00e1sz, L.: The matroid matching problem. In: Lov\u00e1sz, L., S\u00f3s, V.T. (eds.) Algebraic Methods in Graph Theory, Amsterdam (1981)"},{"key":"66_CR29","unstructured":"Marsh III., A.B.: Matching algorithms. PhD thesis, The Johns Hopkins University (1979)"},{"key":"66_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/11841036_48","volume-title":"Algorithms \u2013 ESA 2006","author":"J. Mestre","year":"2006","unstructured":"Mestre, J.: Greedy in approximation algorithms. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 528\u2013539. Springer, Heidelberg (2006)"},{"issue":"3","key":"66_CR31","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G. Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res.\u00a03(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"66_CR32","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G. Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions - i. Math. Prog.\u00a014(1), 265\u2013294 (1978)","journal-title":"Math. Prog."},{"key":"66_CR33","doi-asserted-by":"crossref","unstructured":"Pulleyblank, W.: Faces of matching polyhedra. PhD thesis, Deptartment of Combinatorics and Optimization, University of Waterloo (1973)","DOI":"10.1007\/BFb0066196"},{"key":"66_CR34","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"66_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/3-540-51498-8_39","volume-title":"Fundamentals of Computation Theory","author":"H. Simon","year":"1989","unstructured":"Simon, H.: Approximation algorithms for channel assignment in cellular radio networks. In: Csirik, J., Demetrovics, J., G\u00e8cseg, F. (eds.) FCT 1989. LNCS, vol.\u00a0380, pp. 405\u2013415. Springer, Heidelberg (1989)"},{"key":"66_CR36","doi-asserted-by":"crossref","unstructured":"Soto, J.A.: A simple PTAS for weighted matroid matching on strongly base orderable matroids. To appear in LAGOS (2011)","DOI":"10.1016\/j.endm.2011.05.014"},{"key":"66_CR37","unstructured":"Tong, P., Lawler, E.L., Vazirani, V.V.: Solving the weighted parity problem for gammoids by reduction to graphic matching. Technical Report UCB\/CSD-82-103, EECS Department, University of California, Berkeley (April 1982)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:09:08Z","timestamp":1560528548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}