{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T05:13:30Z","timestamp":1739337210531,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_9","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"95-106","source":"Crossref","is-referenced-by-count":14,"title":["Iterative Rounding for Multi-Objective Optimization Problems"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0305-0548(82)90026-0","volume":"9","author":"V. Aggarwal","year":"1982","unstructured":"Aggarwal, V., Aneja, Y.P., Nair, K.P.K.: Minimal spanning tree subject to a side constraint. Computers & Operations Research\u00a09, 287\u2013296 (1982)","journal-title":"Computers & Operations Research"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive Guarantees for Degree Bounded Directed Network Design. In: STOC, pp. 769\u2013778 (2008)","DOI":"10.1145\/1374376.1374486"},{"issue":"2","key":"9_CR3","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0166-218X(87)90067-9","volume":"16","author":"F. Barahona","year":"1987","unstructured":"Barahona, F., Pulleyblank, W.R.: Exact arborescences, matchings and cycles. Discrete Applied Mathematics\u00a016(2), 91\u201399 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR4","series-title":"Lecture Notes in Economics and Mathematical Systems","volume-title":"Multiobjective Programming and Goal Programming: Theoretical Results and Practical Applications","year":"2009","unstructured":"Barichard, V., Ehrgott, M., Gandibleux, X., T\u2019Kindt, V. (eds.): Multiobjective Programming and Goal Programming: Theoretical Results and Practical Applications. Lecture Notes in Economics and Mathematical Systems, vol.\u00a0618. Springer, Heidelberg (2009)"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1002\/net.3230190402","volume":"19","author":"J.E. Beasley","year":"1989","unstructured":"Beasley, J.E., Christofides, N.: An algorithm for the resource constrained shortest path problem. Networks\u00a019, 379\u2013394 (1989)","journal-title":"Networks"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-68891-4_19","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Berger","year":"2008","unstructured":"Berger, A., Bonifaci, V., Grandoni, F., Sch\u00e4fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 273\u2013287. Springer, Heidelberg (2008)"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-540-27821-4_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"V. Bil\u00f2","year":"2004","unstructured":"Bil\u00f2, V., Goyal, V., Ravi, R., Singh, M.: On the Crossing Spanning Tree Problem. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 51\u201364. Springer, Heidelberg (2004)"},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00493-006-0016-z","volume":"26","author":"J. Cheriyan","year":"2006","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: Network design via iterative rounding of setpair relaxations. Combinatorica\u00a026(3), 255\u2013275 (2006)","journal-title":"Combinatorica"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds.): Pareto Optimality, Game Theory and Equilibria. Optimization and Its Applications, vol.\u00a017 (2008)","DOI":"10.1007\/978-0-387-77247-9"},{"key":"9_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60667-0","volume-title":"Multicriteria Analysis","author":"J. Climacao","year":"1997","unstructured":"Climacao, J.: Multicriteria Analysis. Springer, Heidelberg (1997)"},{"issue":"2","key":"9_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"W.H. Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing Membership in Matroid Polyhedra. Journal of Combinatorial Theory B\u00a036(2), 161\u2013188 (1984)","journal-title":"Journal of Combinatorial Theory B"},{"issue":"5","key":"9_CR12","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1016\/j.jcss.2005.05.006","volume":"72","author":"L. Fleischer","year":"2006","unstructured":"Fleischer, L., Jain, K., Williamson, D.P.: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences\u00a072(5), 838\u2013867 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/net.3230200306","volume":"20","author":"M. Guignard","year":"1990","unstructured":"Guignard, M., Rosenwein, M.B.: An application of Lagrangean decomposition to the resource-constrained minimum weighted arborescence problem. Networks\u00a020, 345\u2013359 (1990)","journal-title":"Networks"},{"key":"9_CR14","first-page":"1","volume-title":"Multiobjective Decision Making","author":"R. Hartley","year":"1983","unstructured":"Hartley, R.: Survey of Algorithms for Vector Optimization Problems. In: French, S., Hartley, R., Thomas, L.C., White, D.J. (eds.) Multiobjective Decision Making, pp. 1\u201334. Academic Press, London (1983)"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica\u00a021, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Naor, S., Salavatipour, M., Singh, M.: Survivable network design with degree or order constraints. In: STOC, pp. 651\u2013660 (2007)","DOI":"10.1145\/1250790.1250886"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: STOC, pp. 759\u2013768 (2008)","DOI":"10.1145\/1374376.1374485"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10107-005-0691-3","volume":"108","author":"A. Levin","year":"2006","unstructured":"Levin, A., Woeginger, G.J.: The constrained minimum weight sum of job completion times. Mathematical Programming\u00a0108, 115\u2013126 (2006)","journal-title":"Mathematical Programming"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-60084-1_99","volume-title":"Automata, Languages and Programming","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Bicriteria network design problems. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 487\u2013498. Springer, Heidelberg (1995)"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1002\/net.20005","volume":"43","author":"V. Melkonian","year":"2004","unstructured":"Melkonian, V., Tardos, E.: Algorithms for a Network Design Problem with Crossing Supermodular Demands. Networks\u00a043, 4 (2004)","journal-title":"Networks"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as Easy as Matrix Inversion. Combinatorica\u00a07(1), 101\u2013104 (1987)","journal-title":"Combinatorica"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of Web sources. In: FOCS, pp. 86\u201392 (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid rumor ramification: Approximating the minimum broadcast time. In: FOCS, pp. 202\u2013213 (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11682462_4","volume-title":"LATIN 2006: Theoretical Informatics","author":"R. Ravi","year":"2006","unstructured":"Ravi, R.: Matching Based Augmentations for Approximating Connectivity Problems. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 13\u201324. Springer, Heidelberg (2006)"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-61422-2_121","volume-title":"Algorithm Theory - SWAT \u201996","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 66\u201375. Springer, Heidelberg (1996)"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Many Birds with One Stone: Multi-objective Approximation Algorithms. In: STOC, pp. 438\u2013447 (1993)","DOI":"10.1145\/167088.167209"},{"key":"9_CR27","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Berlin (2003)"},{"key":"9_CR28","unstructured":"Shmoys, D.B., Tardos, \u00c9.: Scheduling unrelated machines with costs. In: SODA, pp. 448\u2013454 (1993)"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T04:15:39Z","timestamp":1739333739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}