{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T23:27:24Z","timestamp":1667086044816},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,4,15]],"date-time":"2010-04-15T00:00:00Z","timestamp":1271289600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,11]]},"DOI":"10.1007\/s10878-010-9320-z","type":"journal-article","created":{"date-parts":[[2010,4,14]],"date-time":"2010-04-14T15:44:14Z","timestamp":1271259854000},"page":"699-725","source":"Crossref","is-referenced-by-count":4,"title":["Geometric rounding: a dependent randomized rounding scheme"],"prefix":"10.1007","volume":"22","author":[{"given":"Dongdong","family":"Ge","sequence":"first","affiliation":[]},{"given":"Simai","family":"He","sequence":"additional","affiliation":[]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[]},{"given":"Jiawei","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,15]]},"reference":[{"key":"9320_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev AA, Sviridenko MI (2004) Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J Comb Optim 8:307\u2013328","journal-title":"J Comb Optim"},{"key":"9320_CR2","first-page":"184","volume-title":"FOCS \u201996: proceedings of the 37th annual symposium on foundations of computer science","author":"Y Bartal","year":"1996","unstructured":"Bartal Y (1996) Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS \u201996: proceedings of the 37th annual symposium on foundations of computer science, Washington, DC, USA, 1996. IEEE Comput Soc, Los Alamitos, p\u00a0184"},{"key":"9320_CR3","first-page":"192","volume-title":"SODA \u201903: proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms","author":"P Berman","year":"2003","unstructured":"Berman P, Krysta P (2003) Optimizing misdirection. In: SODA \u201903: proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Philadelphia, PA, USA, 2003. Soc for Industr & Appl Math, Philadelphia, pp 192\u2013201"},{"issue":"1","key":"9320_CR4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01582131","volume":"80","author":"D Bertsimas","year":"1998","unstructured":"Bertsimas D, Vohra R (1998) Rounding algorithms for covering problems. Math Program 80(1):63\u201389","journal-title":"Math Program"},{"issue":"2","key":"9320_CR5","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<102::AID-NET3>3.0.CO;2-X","volume":"34","author":"D Bertsimas","year":"1999","unstructured":"Bertsimas D, Teo C, Vohra R (1999a) Analysis of lp relaxations for multiway and multicut problems. Networks 34(2):102\u2013114","journal-title":"Networks"},{"issue":"3","key":"9320_CR6","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","volume":"24","author":"D Bertsimas","year":"1999","unstructured":"Bertsimas D, Teo C, Vohra R (1999b) On dependent randomized rounding algorithms. Oper Res Lett 24(3):105\u2013114","journal-title":"Oper Res Lett"},{"issue":"2","key":"9320_CR7","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1111\/1467-9787.00134","volume":"39","author":"D Bryan","year":"1999","unstructured":"Bryan D, O\u2019Kelly ME (1999) Hub-and-spoke networks in air transportation: an analytical review. J Reg Sci 39(2):275\u2013295","journal-title":"J Reg Sci"},{"key":"9320_CR8","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/276698.276711","volume-title":"STOC \u201998: proceedings of the thirtieth annual ACM symposium on theory of computing","author":"G Calinescu","year":"1998","unstructured":"Calinescu G, Karloff H, Rabani Y (1998) An improved approximation algorithm for multiway cut. In: STOC \u201998: proceedings of the thirtieth annual ACM symposium on theory of computing, New York, NY, USA, 1998. ACM, New York, pp 48\u201352"},{"key":"9320_CR9","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1287\/opre.44.6.923","volume":"44","author":"JF Campbell","year":"1996","unstructured":"Campbell JF (1996) Hub location and the p-hub median problem. Oper Res 44:923\u2013935","journal-title":"Oper Res"},{"key":"9320_CR10","unstructured":"Chekuri C, Khanna S, Naor J, Zosin L (2001) Approximation algorithms for the metric labeling problem via a new linear programming formulation. In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms (SODA), 2001"},{"key":"9320_CR11","doi-asserted-by":"crossref","unstructured":"Devroye L (1986) Non-uniform random variate generation","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"9320_CR12","doi-asserted-by":"crossref","unstructured":"Dobzinski S, Nisan N, Schapira M (2005) Approximation algorithms for combinatorial auctions with complement free bidders. In: Proceedings of the thirty-seventh annual ACM symposium on theory of computing (STOC), pp\u00a0610\u2013618","DOI":"10.1145\/1060590.1060681"},{"issue":"4","key":"9320_CR13","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln\u2009n for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"issue":"3","key":"9320_CR14","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. J ACM 53(3):324\u2013360","journal-title":"J ACM"},{"key":"9320_CR15","unstructured":"Ge D (2009) Geometric rounding: theory and application. PhD thesis"},{"key":"9320_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995a) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42:1115\u20131145","journal-title":"J ACM"},{"issue":"4","key":"9320_CR17","first-page":"565","volume":"7","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995b) New $\\frac{3}{4}$ -approximation algorithms for the maximum satisfiability problem. SIAM J Discrete Math 7(4):565\u2013666","journal-title":"SIAM J Discrete Math"},{"key":"9320_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0053959","volume-title":"APPROX \u201998: proceedings of the international workshop on approximation algorithms for combinatorial optimization","author":"M Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson M (1998) Approximations of independent sets in graphs. In: APPROX \u201998: proceedings of the international workshop on approximation algorithms for combinatorial optimization, London, UK, 1998. Springer, Berlin, pp 1\u201313"},{"key":"9320_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J Hastad","year":"1999","unstructured":"Hastad J (1999) Clique is hard to approximate within n 1\u2212\u03b5 . Acta Math 182:105\u2013142","journal-title":"Acta Math"},{"issue":"3","key":"9320_CR20","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J Comput"},{"issue":"5","key":"9320_CR21","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J Kleinberg","year":"2002","unstructured":"Kleinberg J, Tardos \u00c9 (2002) Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. J ACM 49(5):616\u2013639","journal-title":"J ACM"},{"key":"9320_CR22","first-page":"809","volume-title":"SODA \u201908: proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms","author":"R Krauthgamer","year":"2008","unstructured":"Krauthgamer R, Roughgarden T (2008) Metric clustering via consistent labeling. In: SODA \u201908: proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, Philadelphia, PA, USA, 2008. Soc for Industr & Appl Math, Philadelphia, pp 809\u2013818"},{"key":"9320_CR23","doi-asserted-by":"crossref","unstructured":"Lehmann DJ, O\u2019Callaghan LI, Shoham Y (1999) Truth revelation in approximately efficient combinatorial auctions. In: ACM conference on electronic commerce, pp 96\u2013102","DOI":"10.1145\/336992.337016"},{"key":"9320_CR24","doi-asserted-by":"crossref","unstructured":"O\u2019Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 33","DOI":"10.1016\/S0377-2217(87)80007-3"},{"key":"9320_CR25","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1287\/mnsc.41.4.713","volume":"41","author":"ME O\u2019Kelly","year":"1995","unstructured":"O\u2019Kelly ME, Skorin-Kapov J, Skorin-Kapov D (1995) Lower bounds for the hub location problem. Manage Sci 41:713\u2013728","journal-title":"Manage Sci"},{"issue":"2","key":"9320_CR26","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(2):130\u2013143","journal-title":"J Comput Syst Sci"},{"key":"9320_CR27","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan P, Thompson CD (1987) Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7:365\u2013374","journal-title":"Combinatorica"},{"key":"9320_CR28","volume-title":"Introduction to probability models","author":"SM Ross","year":"2006","unstructured":"Ross SM (2006) Introduction to probability models, 9th edn. Academic Press, Orlando","edition":"9"},{"issue":"3","key":"9320_CR29","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys DB, Tardos \u00c9 (1993) An approximation algorithm for the generalized assignment problem. Math Program 62(3):461\u2013474","journal-title":"Math Program"},{"key":"9320_CR30","unstructured":"Srinivasan A (1996) An extension of the lov\u00e1sz local lemma, and its applications to integer programming. In: SODA \u201996: proceedings of the seventh annual ACM-SIAM symposium on discrete algorithms, Philadelphia, PA, USA, pp 6\u201315"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9320-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-010-9320-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9320-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:16Z","timestamp":1559276296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-010-9320-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,15]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9320"],"URL":"https:\/\/doi.org\/10.1007\/s10878-010-9320-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,15]]}}}