{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T04:29:38Z","timestamp":1749184178171,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_61","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"689-701","source":"Crossref","is-referenced-by-count":51,"title":["Online Primal-Dual Algorithms for Covering and Packing Problems"],"prefix":"10.1007","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"61_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. In: The 35th annual ACM Symp. on the Theory of Computation (2003)","DOI":"10.1145\/780542.780558"},{"key":"61_CR2","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. In: SODA (2004)"},{"key":"61_CR3","unstructured":"Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized steiner problem. In: Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (1996)"},{"key":"61_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive online routing. In: Proc. of 34th FOCS, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"key":"61_CR5","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorithms for steiner tree problems. In: Proc. of the 29th annual ACM Symp. on the Theory of Computation (1997)","DOI":"10.1145\/258533.258618"},{"key":"61_CR6","unstructured":"Fleischer, L.: A fast approximation scheme for fractional covering problems with variable upper bounds. In: SODA 2004, pp. 1001\u20131010 (2004)"},{"key":"61_CR7","doi-asserted-by":"crossref","unstructured":"Fleischer, L.K.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics (2000)","DOI":"10.1137\/S0895480199355754"},{"key":"61_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-30140-0_34","volume-title":"Algorithms \u2013 ESA 2004","author":"N. Garg","year":"2004","unstructured":"Garg, N., Khandekar, R.: Fractional covering with upper bounds on the variables: Solving lps with negative entries. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 371\u2013382. Springer, Heidelberg (2004)"},{"key":"61_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N., Konemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: FOCS 1998, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"key":"61_CR10","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"Imase, M., Waxman, B.: Dynamic steiner tree problem. SIAM Journal Discrete Math.\u00a04, 369\u2013384 (1991)","journal-title":"SIAM Journal Discrete Math."},{"key":"61_CR11","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G., Young, N.E.: Tight approximation results for general covering integer programs. In: FOCS 2001, pp. 522\u2013528 (2001)","DOI":"10.1109\/SFCS.2001.959928"},{"issue":"2","key":"61_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci.\u00a037(2), 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"61_CR13","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"61_CR14","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"E.T.S. Plotkin","year":"1995","unstructured":"Plotkin, E.T.S., Shmoys, D.: Fast approximation algorithms for fractional packing and covering problems. Math. of Operations Research\u00a020, 257\u2013301 (1995)","journal-title":"Math. of Operations Research"},{"issue":"2","key":"61_CR15","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 Journal on Computing\u00a029(2), 648\u2013670 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"61_CR16","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In: Proc. of the 6th annual ACM-SIAM symp. on Discrete algorithms, pp. 170\u2013178 (1995)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T20:09:40Z","timestamp":1736021380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11561071_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}