{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:31:35Z","timestamp":1740547895373,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220572"},{"type":"electronic","value":"9783540247678"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24767-8_81","type":"book-chapter","created":{"date-parts":[[2010,9,11]],"date-time":"2010-09-11T00:45:04Z","timestamp":1284165904000},"page":"764-775","source":"Crossref","is-referenced-by-count":3,"title":["Packing: Scheduling, Embedding, and Approximating Metrics"],"prefix":"10.1007","author":[{"given":"Hu","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"81_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/3-540-61440-0_159","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"1996","unstructured":"Alon, N., Srinivasan, A.: Improved parallel approximation of a class of integer programming problems. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 562\u2013573. Springer, Heidelberg (1996)"},{"key":"81_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1287\/ijoc.3.2.149","volume":"3","author":"D. Applegate","year":"1991","unstructured":"Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA Journal of Computing\u00a03, 149\u2013156 (1991)","journal-title":"ORSA Journal of Computing"},{"key":"81_CR3","doi-asserted-by":"crossref","unstructured":"Baltz, A., Srivastav, A.: Fast Approximation of Minimum Multicast Congestion \u2013 Implementation versus Theory. In: Proceedings of the 5th Conference on Algorithms and Complexity, CIAC 2003 (2003)","DOI":"10.1007\/3-540-44849-7_22"},{"key":"81_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1996, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"81_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998 (1998)","DOI":"10.1145\/276698.276725"},{"key":"81_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1287\/mnsc.35.2.164","volume":"35","author":"J. Carlier","year":"1989","unstructured":"Carlier, J., Pinson, E.: An algorithm for solving the job-shop problem. Management Science\u00a035, 164\u2013176 (1989)","journal-title":"Management Science"},{"key":"81_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998 (1998)","DOI":"10.1145\/276698.276719"},{"key":"81_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1998, pp. 379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"81_CR9","doi-asserted-by":"publisher","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"6","author":"G. Even","year":"1999","unstructured":"Even, G., Naor, J.S., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM. Journal on Computing\u00a06, 2187\u20132214 (1999)","journal-title":"SIAM. Journal on Computing"},{"key":"81_CR10","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness, W","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computer and Intractability: A Guide to the Theory of NP-Completeness, W. W. H. Freeman and Company, NY (1979)"},{"key":"81_CR11","doi-asserted-by":"crossref","unstructured":"Garg, N., K\u00f6nemann, J.: Fast and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 39th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1998, pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"key":"81_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0895480199326104","volume":"14","author":"L.A. Goldberg","year":"2001","unstructured":"Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM Journal on Discrete Mathematics\u00a014, 67\u201392 (2001)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"81_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"2","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Coordination complexity of parallel pricedirective decomposition. Mathematics of Operations Research\u00a02, 321\u2013340 (1996)","journal-title":"Mathematics of Operations Research"},{"key":"81_CR14","first-page":"477","volume":"75","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Approximate minimum-cost multicommodity flows in O(\u03b5\u22122knm) time. Mathematical Programming\u00a075, 477\u2013482 (1996)","journal-title":"Mathematical Programming"},{"key":"81_CR15","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"T.C. Hu","year":"1974","unstructured":"Hu, T.C.: Optimum communication spanning trees. SIAM Journal on Computing\u00a03, 188\u2013195 (1974)","journal-title":"SIAM Journal on Computing"},{"key":"81_CR16","unstructured":"Jansen, K.: Approximation algorithms for fractional covering and packing problems, and applications (2003) (manuscript)"},{"key":"81_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/3-540-36136-7_16","volume-title":"Algorithms and Computation","author":"K. Jansen","year":"2002","unstructured":"Jansen, K., Solis-Oba, R.: An asymptotic fully polynomial time approximation scheme for bin covering. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 175\u2013186. Springer, Heidelberg (2002)"},{"key":"81_CR18","doi-asserted-by":"crossref","unstructured":"Jansen, K., Zhang, H.: Approximation algorithms for general packing problems with modified logarithmic potential function. In: Proceedings of 2nd IFIP International Conference on Theoretical Computer Science, TCS 2002 (2002)","DOI":"10.1007\/978-0-387-35608-2_22"},{"key":"81_CR19","unstructured":"Jansen, K., Zhang, H.: An approximation algorithm for the multicast congestion problem via minimum Steiner trees. In: Proceedings of 3rd International Workshop on Approximation and Randomized Algorithms in Communication Networks, ARANCE 2002 (2002)"},{"key":"81_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume-title":"Handbooks in Operations Research and Management Science: Logistics of Production and Inventory","author":"E.L. Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., et al. (eds.) Handbooks in Operations Research and Management Science: Logistics of Production and Inventory, vol.\u00a04, pp. 445\u2013522. Elsevier, Amsterdam (1993)"},{"key":"81_CR21","doi-asserted-by":"crossref","unstructured":"Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS 1998, pp. 422\u2013431 (1988)","DOI":"10.1109\/SFCS.1988.21958"},{"key":"81_CR22","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"24","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming\u00a024, 259\u2013272 (1990)","journal-title":"Mathematical Programming"},{"key":"81_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"2","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, E.: Fast Approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a02, 257\u2013301 (1995)","journal-title":"Mathematics of Operations Research"},{"key":"81_CR24","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. Journal of Computer and System Science\u00a037, 130\u2013143 (1988)","journal-title":"Journal of Computer and System Science"},{"key":"81_CR25","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":"81_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"J.P. Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics\u00a08, 223\u2013250 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"81_CR27","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D.B. Shmoys","year":"1994","unstructured":"Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing\u00a023, 617\u2013632 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"81_CR28","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: Speeding up linear programming using fast matrix multiplication. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1998, pp. 332\u2013337 (1989)","DOI":"10.1109\/SFCS.1989.63499"},{"key":"81_CR29","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1989, pp. 338\u2013343 (1989)","DOI":"10.1109\/SFCS.1989.63500"},{"key":"81_CR30","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-642-99789-1_25","volume-title":"Applied Mathematics and Parallel Computing \u2013 Festschrift for Klaus Ritter","author":"J. Villavicencio","year":"1996","unstructured":"Villavicencio, J., Grigoriadis, M.D.: Approximate structured optimization by cyclic block-coordinate descent. In: Fischer, H., et al. (eds.) Applied Mathematics and Parallel Computing \u2013 Festschrift for Klaus Ritter, pp. 359\u2013371. Physica-Verlag, Heidelberg (1996)"},{"key":"81_CR31","series-title":"Lecture Notes in Economics and Mathematical Systems","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/978-3-642-59179-2_23","volume-title":"Network Optimization","author":"J. Villavicencio","year":"1997","unstructured":"Villavicencio, J., Grigoriadis, M.D.: Approximate Lagrangian decomposition with a modified Karmarkar logarithmic potential. In: Pardalos, P., Hearn, D.W., Hager, W.W. (eds.) Network Optimization. Lecture Notes in Economics and Mathematical Systems, vol.\u00a0450, pp. 471\u2013485. Springer, Berlin (1997)"},{"key":"81_CR32","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"D.P. Williamson","year":"1997","unstructured":"Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A., Lenstra, J.K., Sevast\u2019yanov, S.V., Shmoys, D.B.: Short shop schedules. Operations Research\u00a045, 288\u2013294 (1997)","journal-title":"Operations Research"},{"key":"81_CR33","unstructured":"Wu, B.Y., Lancia, G., Bafna, V., Chao, K., Ravi, R., Tang, C.Y.: A polynomial time approximation scheme for minimum routing cost spanning trees. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998 (1998)"},{"key":"81_CR34","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, pp. 170\u2013178 (1995)"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications \u2013 ICCSA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24767-8_81.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T18:06:23Z","timestamp":1740506783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24767-8_81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220572","9783540247678"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24767-8_81","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}