{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:31:00Z","timestamp":1759847460875},"reference-count":20,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7894,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The star\u2010star concentrator location problem (SSCLP), which is a network layout problem, is considered. SSCLP is formulated as an integer linear programming problem. The Lagrangian relaxation (LR) method is used to obtain suboptimal solutions (upper bounds) and lower bounds. Three different LRs are used for SSCLP. The resulting Lagrangian dual problems are shown to be equivalent to some linear programming problems. An approximation algorithm is suggested for SSCLP that produces both a feasible solution (upper bound) and a lower bound. It is shown that if <jats:styled-content><jats:italic>z<\/jats:italic><\/jats:styled-content> and z\u0304are the lower and upper bounds found, then z\u0304\/<jats:styled-content><jats:italic>z<\/jats:italic><\/jats:styled-content> \u2264 <jats:italic>k<\/jats:italic>, where <jats:italic>k<\/jats:italic> is the concentrator capacity. Some computational examples with up to 50 terminals and 20 potential concentrator sites are considered. All the network designs obtained are shown to be within 2.8% of optimal.<\/jats:p>","DOI":"10.1002\/net.3230150102","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T18:49:37Z","timestamp":1178909377000},"page":"1-20","source":"Crossref","is-referenced-by-count":81,"title":["Lagrangian relaxation for the star\u2010star concentrator location problem: Approximation algorithm and bounds"],"prefix":"10.1002","volume":"15","author":[{"given":"Andranik","family":"Mirzaian","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho V. A.","year":"1974"},{"key":"e_1_2_1_3_2","volume-title":"Optimization of concentrator location in teleprocessing networks, in Proceedings, Symposium on Computer Communications and Teletraffic","author":"Bahl L. R.","year":"1972"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093708"},{"key":"e_1_2_1_5_2","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds J.","year":"1971"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.361"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.6.992"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.9.670"},{"key":"e_1_2_1_10_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1013001"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_13_2","volume-title":"Location on Networks: Theory and Algorithms","author":"Handler G. Y.","year":"1979"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.12.B718"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.643"},{"key":"e_1_2_1_18_2","unstructured":"A.Mirzaian Topological optimization of computer communication networks: Approximate algorithms and bounds. Ph. D. Thesis Princeton University (1981)."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1094884"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_21_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T15:44:49Z","timestamp":1697816689000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,3]]}},"alternative-id":["10.1002\/net.3230150102"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150102","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,3]]}}}