{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:19Z","timestamp":1725558919457},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540245742"},{"type":"electronic","value":"9783540318330"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31833-0_11","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T18:11:05Z","timestamp":1278094265000},"page":"111-125","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints"],"prefix":"10.1007","author":[{"given":"Hadas","family":"Shachnai","sequence":"first","affiliation":[]},{"given":"Oded","family":"Shmueli","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Sayegh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Akbar, M.M., Manning, E.G., Shoja, G.C., Khan, S.: Heuristic Solutions for the Multiple-Choice Multi-Dimension Knapsack Problem. In: Int. Conference on Computational Science, vol.\u00a0(2), pp. 659\u2013668 (2001)","DOI":"10.1007\/3-540-45718-6_71"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Bichler, M., Kalagnanam, J., Lee, H.S., Lee, J.: Winner Determination Algorithms for Electronic Auctions: A Framework Design. In: EC-Web, pp. 37\u201346 (2002)","DOI":"10.1007\/3-540-45705-4_5"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(76)90048-7","volume":"3","author":"A.K. Chandra","year":"1976","unstructured":"Chandra, A.K., Hirschberg, D.S., Wong, C.K.: Approximate Algorithms for Some Generalized Knapsack Problems. Theoretical Computer Science\u00a03, 293\u2013304 (1976)","journal-title":"Theoretical Computer Science"},{"key":"11_CR4","unstructured":"Chekuri, C., Khanna, S.: A PTAS for the Multiple Knapsack Problem. In: Proc. of SODA, pp. 213\u2013222 (2000)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A Greedy Heuristic for the Set Covering Problem. Math. Oper. Res.\u00a04, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G. Dobson","year":"1982","unstructured":"Dobson, G.: Worst-case Analysis of Greedy for Integer Programming with Nonnegative Data. Math. of Operations Research\u00a07, 515\u2013531 (1982)","journal-title":"Math. of Operations Research"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"A.M. Frieze","year":"1984","unstructured":"Frieze, A.M., Clarke, M.R.B.: Approximation Algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses. European J. of Operational Research\u00a015(1), 100\u2013109 (1984)","journal-title":"European J. of Operational Research"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. In: Proc. of 28th Symposium on Theory of Computing, pp. 314\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"key":"11_CR9","unstructured":"Fleischer, L.: A Fast Approximation Scheme for Fractional Covering Problems with Variable Upper Bounds. In: Proc. of SODA, pp. 994\u20131003 (2004)"},{"key":"11_CR10","volume-title":"Computers and intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"28","DOI":"10.15807\/jorsj.23.28","volume":"23","author":"T. Ibaraki","year":"1980","unstructured":"Ibaraki, T.: Approximate algorithms for the multiple-choice continuous knapsack problems. J. of Operations Research Society of Japan\u00a023, 28\u201362 (1980)","journal-title":"J. of Operations Research Society of Japan"},{"key":"11_CR12","first-page":"59","volume":"21","author":"T. Ibaraki","year":"1978","unstructured":"Ibaraki, T., Hasegawa, T., Teranaka, K., Iwase, J.: The Multiple Choice Knapsack Problem. J. Oper. Res. Soc. Japan\u00a021, 59\u201394 (1978)","journal-title":"J. Oper. Res. Soc. Japan"},{"issue":"2\u20133","key":"11_CR13","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/S0166-218X(02)00598-X","volume":"129","author":"S.G. Kolliopoulos","year":"2003","unstructured":"Kolliopoulos, S.G.: Approximating covering integer programs with multiplicity constraints. Discrete Applied Math.\u00a0129(2\u20133), 461\u2013473 (2003)","journal-title":"Discrete Applied Math."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G., Young, N.E.: Tight Approximation Results for General Covering Integer Programs. In: Proc. of FOCS, pp. 522\u2013528 (2001)","DOI":"10.1109\/SFCS.2001.959928"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Kothari, A., Parkes, D., Suri, S.: Approximately-Strategyproof and Tractable Multi-Unit Auctions. In: Proc. of ACM-EC (2003)","DOI":"10.1145\/779928.779948"},{"key":"11_CR16","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Metroids. Holt, Reinhart and Winston (1976)"},{"key":"11_CR17","unstructured":"Lueker, G.S.: Two NP-complete problems in nonnegative integer programming. Report # 178, Computer science Lab., Princeton Univ. (1975)"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/S0097539793260763","volume":"28","author":"S. Rajagopalan","year":"1998","unstructured":"Rajagopalan, S., Vazirani, V.V.: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. SIAM J. Comput.\u00a028(2), 525\u2013540 (1998)","journal-title":"SIAM J. Comput."},{"key":"11_CR19","unstructured":"Shachnai, H., Shmueli, O., Sayegh, R.: Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints, full version, http:\/\/www.cs.technion.ac.il\/~hadas\/PUB\/ds.ps"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-540-45198-3_15","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"H. Shachnai","year":"2003","unstructured":"Shachnai, H., Tamir, T.: Approximation Schemes for Generalized 2-dimensional Vector Packing with Application to Data Placement. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 165\u2013177. Springer, Heidelberg (2003)"},{"key":"11_CR21","unstructured":"Srinivasan, A.: An Extension of the Lov\u00e1sz Local Lemma, and its Applications to Integer Programming. In: Proc. of SODA, pp. 6\u201315 (1996)"},{"issue":"2","key":"11_CR22","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved Approximation Guarantees for Packing and Covering Integer Programs. SIAM J. Comput.\u00a029(2), 648\u2013670 (1999)","journal-title":"SIAM J. Comput."},{"key":"11_CR23","unstructured":"Shmueli, O., Golany, B., Sayegh, R., Shachnai, H., Perry, M., Gradovitch, N., Yehezkel, B.: Negotiation Platform. International Patent Application WO 02077759 (2001-2002)"},{"key":"11_CR24","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1111\/j.1467-6419.1996.tb00018.x","volume":"10","author":"E. Wolfstetter","year":"1996","unstructured":"Wolfstetter, E.: Auctions: An Introduction. J. of Economic Surveys\u00a010, 367\u2013420 (1996)","journal-title":"J. of Economic Surveys"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31833-0_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:27:39Z","timestamp":1605760059000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31833-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540245742","9783540318330"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31833-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}