{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:01:47Z","timestamp":1737090107269,"version":"3.33.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,5,8]],"date-time":"2007-05-08T00:00:00Z","timestamp":1178582400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s10107-007-0106-8","type":"journal-article","created":{"date-parts":[[2007,5,7]],"date-time":"2007-05-07T14:12:22Z","timestamp":1178547142000},"page":"183-206","source":"Crossref","is-referenced-by-count":9,"title":["Approximation algorithms for general packing problems and their application to the multicast congestion problem"],"prefix":"10.1007","volume":"114","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hu","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,5,8]]},"reference":[{"key":"106_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora S., Lund C., Motwani R., Sudan M. and Szegedy M. (1998). Proof verification and hardness of approximation problems. J. Assoc. Comput. Mach. 45: 501\u2013555","journal-title":"J. Assoc. Comput. Mach."},{"key":"106_CR2","unstructured":"Baltz, A., Srivastav, A.: Fast approximation of multicast congestion, Manuscript (2001)"},{"key":"106_CR3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1051\/ro:2004028","volume":"38","author":"A. Baltz","year":"2004","unstructured":"Baltz A. and Srivastav A. (2004). Fast approximation of minimum multicast congestion\u2014implementation versus theory. RAIRO Oper. Res. 38: 319\u2013344","journal-title":"RAIRO Oper. Res."},{"key":"106_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern M. and Plassmann P. (1989). The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32: 171\u2013176","journal-title":"Inf. Process. Lett."},{"key":"106_CR5","volume-title":"Numerical analysis, 6th edn","author":"R.L. Burden","year":"1997","unstructured":"Burden R.L. and Faires J.D. (1997). Numerical analysis, 6th edn. Brooks\/Cole publishing company, Baltimore\/Three Lakes"},{"key":"106_CR6","doi-asserted-by":"crossref","unstructured":"Carr, R., Vempala, S.: Randomized meta-rounding. In: Proceedings of the 32nd ACM Symposium on the Theory of Computing, STOC, pp 58\u201362 (2000)","DOI":"10.1145\/335305.335312"},{"key":"106_CR7","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, pp 379\u2013388(1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"106_CR8","doi-asserted-by":"crossref","unstructured":"Chleb\u00ed k, M., Chleb\u00ed kov\u00e1, J.: Approximation hardness of the Steiner tree problem. In: Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, SWAT, LNCS, vol. 2368, pp 170\u2013179 (2002)","DOI":"10.1007\/3-540-45471-3_18"},{"issue":"4","key":"106_CR9","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.jpdc.2005.10.010","volume":"66","author":"J. Chleb\u00ed kov\u00e1","year":"2006","unstructured":"Chleb\u00ed kov\u00e1 J., Ye D. and Zhang H. (2006). Assign ranges in general ad-hoc networks. J. Parallel Distrib. Comput. 66(4): 489\u2013498","journal-title":"J. Parallel Distrib. Comput."},{"key":"106_CR10","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"6","author":"G. Even","year":"1999","unstructured":"Even G., Naor J.S., Rao S. and Schieber B. (1999). Fast approximate graph partitioning algorithms. SIAM J. Comput. 6: 2187\u20132214","journal-title":"SIAM J. Comput."},{"key":"106_CR11","unstructured":"Fleischer, L.: A fast approximation scheme for fractional covering problems with variable upper bounds. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 994\u20131003 (2004)"},{"key":"106_CR12","doi-asserted-by":"crossref","unstructured":"Garg, N., Khandekar, R.: Fractional covering with upper bounds on the variables: solving LPs with negative entries. In: Proceedings of the 12th Annual European Symposium on Algorithms, ESA, LNCS, vol. 3221, pp 371\u2013382 (2004)","DOI":"10.1007\/978-3-540-30140-0_34"},{"key":"106_CR13","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, pp 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"key":"106_CR14","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"M.D. Grigoriadis","year":"1994","unstructured":"Grigoriadis M.D. and Khachiyan L.G. (1994). Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4: 86\u2013107","journal-title":"SIAM J. Optim."},{"key":"106_CR15","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"2","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis M.D. and Khachiyan L.G. (1996). Coordination complexity of parallel price-directive decomposition. Math. Oper. Res. 2: 321\u2013340","journal-title":"Math. Oper. Res."},{"key":"106_CR16","first-page":"477","volume":"75","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis M.D. and Khachiyan L.G. (1996). Approximate minimum-cost multicommodity flows in O(\u03b5\u22122 knm) time. Math. Programm. 75: 477\u2013482","journal-title":"Math. Programm."},{"key":"106_CR17","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1137\/S1052623499358689","volume":"11","author":"M.D. Grigoriadis","year":"2001","unstructured":"Grigoriadis M.D., Khachiyan L.G., Porkolab L. and Villavicencio J. (2001). Approximate max\u2013min resource sharing for structured concave optimization. SIAM J. Optim. 11: 1081\u20131091","journal-title":"SIAM J. Optim."},{"key":"106_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L. and Schrijver A. (1988). Geometric Algorithms and Combinatorial Optimization. Springer, Berlin"},{"key":"106_CR19","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0304-3975(02)00829-0","volume":"302","author":"K. Jansen","year":"2003","unstructured":"Jansen K. (2003). Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theor. Comput. Sci. 302: 239\u2013256","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"106_CR20","first-page":"547","volume":"106","author":"K. Jansen","year":"2006","unstructured":"Jansen K. (2006). An approximation algorithm for the general max\u2013min resource sharing problem. Math. 106(3): 547\u2013566","journal-title":"Math."},{"key":"106_CR21","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/030601570","volume":"17","author":"K. Jansen","year":"2006","unstructured":"Jansen K. (2006). Approximation algorithm for the mixed fractional packing and covering problem. SIAM. J. Optim. 17: 331\u2013352","journal-title":"SIAM. J. Optim."},{"key":"106_CR22","unstructured":"Diedrich, F., Jansen, K., Faster and simpler approximation algorithms for mixed packing and covering problems, to appear in Theoretical Computer Science."},{"key":"106_CR23","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1287\/moor.26.2.324.10559","volume":"26","author":"K. Jansen","year":"2001","unstructured":"Jansen K. and Porkolab L. (2001). Improved approximation schemes for scheduling unrelated parallel machines. Math. Oper. Res. 26: 324\u2013338","journal-title":"Math. Oper. Res."},{"key":"106_CR24","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480101396949","volume":"20","author":"K. Jansen","year":"2006","unstructured":"Jansen K. and Porkolab L. (2006). On preemptive resource constrained scheduling: polynomial time schemes. SIAM. J. Discrete. Math. 20: 545\u2013563","journal-title":"SIAM. J. Discrete. Math."},{"key":"106_CR25","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1016\/S0304-3975(03)00363-3","volume":"306","author":"K. Jansen","year":"2003","unstructured":"Jansen K. and Solis-Oba R. (2003). An asymptotic fully polynomial time approximation scheme for bin covering. Theor. Comput. Sci. 306: 543\u2013551","journal-title":"Theor. Comput. Sci."},{"key":"106_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp R.M. (1972). Reducibility among combinatorial problems. In: Miller, R.E. and Thatcher, J.W. (eds) Complexity of Computer Computations, pp 85\u2013103. Plenum Press, New York"},{"key":"106_CR27","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/S0097539792241175","volume":"23","author":"P. Klein","year":"1994","unstructured":"Klein P., Plotkin S., Stein C. and Tardos E. (1994). Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput. 23: 466\u2013487","journal-title":"SIAM J. Comput."},{"key":"106_CR28","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"24","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra J.K., Shmoys D.B. and Tardos E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 24: 259\u2013272","journal-title":"Math. Program."},{"key":"106_CR29","doi-asserted-by":"crossref","unstructured":"Lu, Q., Zhang, H.: Implementation of approximation algorithms for the multicast congestion problem. In: Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms, WEA, LNCS, vol. 3503, pp 152\u2013164 (2005)","DOI":"10.1007\/11427186_15"},{"key":"106_CR30","doi-asserted-by":"crossref","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. and Tardos E. (1995). Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 2: 257\u2013301","journal-title":"Math. Oper. Res."},{"key":"106_CR31","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0025-5610(96)00072-X","volume":"78","author":"T. Radzik","year":"1997","unstructured":"Radzik T. (1997). Fast deterministic approximation for the multicommodity flow problem. Math. Program. 78: 43\u201358","journal-title":"Math. Program."},{"key":"106_CR32","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan P. (1988). Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37: 130\u2013143","journal-title":"J. Comput. Syst. Sci."},{"key":"106_CR33","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan P. and Thompson C. (1987). Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7: 365\u2013374","journal-title":"Combinatorica"},{"key":"106_CR34","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 770\u2013779 (2000)"},{"key":"106_CR35","doi-asserted-by":"crossref","unstructured":"Terlaky, T., Vannelli, A., Zhang, H.: On routing in VLSI design and communication networks. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation, ISAAC, LNCS, vol. 3827, pp 1051\u20131060 (2005)","DOI":"10.1007\/11602613_104"},{"key":"106_CR36","doi-asserted-by":"crossref","unstructured":"Vempala, S., V\u00f6cking, B.: Approximating multicast congestion. In: Proceedings of the tenth International Symposium on Algorithms and Computation, ISAAC, LNCS, vol. 1741, pp 367\u2013372 (1999)","DOI":"10.1007\/3-540-46632-0_37"},{"key":"106_CR37","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-642-99789-1_25","volume-title":"Applied Mathematics and Parallel Computing\u2014Festschrift","author":"J. Villavicencio","year":"1996","unstructured":"Villavicencio J. and Grigoriadis M.D. (1996). Approximate structured optimization by cyclic block-coordinate descent. In: Ritter, K., Fischer, H., Riedm\u00fcller, B. and Sch\u00e4ffler, S. (eds) Applied Mathematics and Parallel Computing\u2014Festschrift, pp 359\u2013371. Physica-Verlag, Heidelberg"},{"key":"106_CR38","first-page":"471","volume-title":"Network Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 450","author":"J. Villavicencio","year":"1997","unstructured":"Villavicencio J. and Grigoriadis M.D. (1997). Approximate Lagrangian decomposition with a modified Karmarkar logarithmic potential. In: Pardalos, P., Hearn, D.W. and Hager, W.W. (eds) Network Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 450, pp 471\u2013485. Springer, Berlin"},{"key":"106_CR39","doi-asserted-by":"crossref","unstructured":"Ye, D., Zhang, H.: The range assignment problem in static ad-hoc networks on metric spaces. In: Proceedings of the 11th Colloquium on Structural Information and Communication Complexity, SIROCCO, LNCS, vol. 3104, pp 291\u2013302 (2004)","DOI":"10.1007\/978-3-540-27796-5_26"},{"key":"106_CR40","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp 170\u2013178 (1995)"},{"key":"106_CR41","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp 538\u2013546 (2001)","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0106-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-007-0106-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0106-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T02:30:15Z","timestamp":1736994615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-007-0106-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,8]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["106"],"URL":"https:\/\/doi.org\/10.1007\/s10107-007-0106-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2007,5,8]]}}}