{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:54:28Z","timestamp":1649120068654},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p> The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. It enables us to obtain quasi-polynomial-time approximation schemes for basic variants of the buy-at-bulk geometric network design problem with polynomial total demand. Then, for instances with a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms. <\/jats:p>","DOI":"10.1142\/s0129054111009148","type":"journal-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T12:46:00Z","timestamp":1326199560000},"page":"1949-1969","source":"Crossref","is-referenced-by-count":1,"title":["APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN"],"prefix":"10.1142","volume":"22","author":[{"given":"ARTUR","family":"CZUMAJ","sequence":"first","affiliation":[{"name":"Centre for Discrete Mathematics and its Applications (DIMAP) and Department of Computer Science, University of Warwick, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUREK","family":"CZYZOWICZ","sequence":"additional","affiliation":[{"name":"Departement d'Informatique, Universite du Quebec en Outaouais, Gatineau, Quebec J8X 3X7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LESZEK","family":"G\u0104SIENIEC","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Peach Street, L69 7ZF, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JESPER","family":"JANSSON","sequence":"additional","affiliation":[{"name":"Ochanomizu University, 2-1-1 Otsuka, Bunkyo-ku, Tokyo-112-8610, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANDRZEJ","family":"LINGAS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, 22100 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAWEL","family":"ZYLINSKI","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Gda\u0144sk, 80-952 Gda\u0144sk, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"rf8","first-page":"177","volume":"81","author":"Bienstock D.","journal-title":"Mathematical Programming"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/090750317"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00024-9"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.02.001"},{"key":"rf15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322124"},{"key":"rf27","unstructured":"R. M.\u00a0Karp and J. M.\u00a0Steele, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, eds. E. L.\u00a0Lawler (John Wiley & Sons Ltd., 1985)\u00a0pp. 181\u2013205."},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014554606793"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.005"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1002\/net.1026"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111009148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:13:28Z","timestamp":1565129608000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111009148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":16,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S0129054111009148"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111009148","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}