{"entities":{"Q2224275":{"pageid":2235018,"ns":120,"title":"Item:Q2224275","lastrevid":73832286,"modified":"2026-04-14T17:25:30Z","type":"item","id":"Q2224275","labels":{"en":{"language":"en","value":"An efficient approximation algorithm for the extension facility location problem on torus internetwork topology"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7305534"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$47DC4DCA-FF1C-4B89-BABE-3E3946152198","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de3b8d93152d6895755d3be2dd7436fbbda44fbd","datavalue":{"value":{"text":"An efficient approximation algorithm for the extension facility location problem on torus internetwork topology","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2224275$E5A69951-FBA7-43EF-99BF-EBDB88400AC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6a35fa732dc155694c37e0b1ee429b4be421279e","datavalue":{"value":"1453.90097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224275$8446BA47-73F3-4091-8291-C0D78814A200","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae28fc5a5f935fbfe416d3f18d6e5b82c30f0a4c","datavalue":{"value":"10.1504/IJCSM.2018.091736","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224275$70ED19D3-FB63-4E62-9375-2BEDBC53A3A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"327cf8ed3d36c36e8a790ee6a373ffd4efd6f7fe","datavalue":{"value":{"entity-type":"item","numeric-id":1933427,"id":"Q1933427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$6552E896-CF49-45DB-A94F-5C31EF94257F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6d006ea6116f29e36f0326e4a6cc226abee6c7e","datavalue":{"value":{"entity-type":"item","numeric-id":1933426,"id":"Q1933426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$1C246C48-34F5-4E1E-8F5E-65938D87E1CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1291677fed0e573141a6813cd43dece80339c0c6","datavalue":{"value":{"entity-type":"item","numeric-id":181203,"id":"Q181203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$8A9A9A7A-F548-4FF4-BD10-A3B62D7923F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f306f7a0701f0c426c5681c314795b1e314a5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":391694,"id":"Q391694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$F5AE8523-DAC9-4992-A962-1045AC6A184D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4fdcf569a0845156edf00801a6025e0e3cf1d2e","datavalue":{"value":{"time":"+2021-02-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2224275$421B4C5C-6167-4073-9EBB-06BE8D172FA3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db13b69ba24521465def5ad089beabd0a3cf6cd1","datavalue":{"value":"Summary: The uncapacitated facility location problem is an NP-hard problem. Nowadays there are few studies on this problem in practical applications on the torus internetwork topology. The objective of this paper is to extend the facility location problem on the two-dimensional torus internetwork topology. At first, the extension facility location problem with two additional constraints is formulated as integer linear programming. Then, two embedding schemes are proposed respectively by partitioning the solutions of the extension problem into stars, which exhibit a trade-off between dilation and expansion. Finally, an efficient approximation algorithm is developed to find the integer solutions of the extension facility location problem. Moreover, the relative analysis of approximation guarantee of the proposed algorithm is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$ECB770CC-D87C-4D70-9F21-72C1EC536F44","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224275$1FFD2739-3F1E-4A1F-9733-B310FC8E6ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224275$30022A6A-5AE6-48D7-8A70-A03B29C3EFB4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fbbbba4619f9542d1fa26704e5a0c8570cb17cd8","datavalue":{"value":"7305534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224275$03C2CBC6-E684-4FF1-B7EF-8E72E0E071AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dc76359e1b247b8a96b03ef98bc894d41ad211f","datavalue":{"value":"facility location","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$91A7AB0D-4853-4337-A637-07B101356D7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$935A22EC-B658-4D91-A49B-6C3ABB2752C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b06ccee7b4314e226680451cd9a6596d61d1738a","datavalue":{"value":"embedding scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$CAFF5D50-82E4-4FD6-B6F6-B4A1B0ED464A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf6c4e1b24b703c3f1e0299729a0c8329c1f97fd","datavalue":{"value":"torus internetwork topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$66A842FA-D5F6-4E14-A101-7FECB10E2B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224275$F7F120A7-974C-4AF7-9F5D-D6604A94B369","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224275$006AE046-CDA8-4931-9265-455651153065","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ceea42f661f00a15487113c280a595e61e3bd31","datavalue":{"value":{"entity-type":"item","numeric-id":1667394,"id":"Q1667394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfabf68ddd3b3a8477572c1e16c15b105c232356","datavalue":{"value":{"amount":"+0.87365544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$3078E5A8-404F-49C3-B39C-5F24160627E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c8fad3b39e5d8813de66b8be30d6db3af0442ac","datavalue":{"value":{"entity-type":"item","numeric-id":3611984,"id":"Q3611984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ab3f9b49b983776603723be2339514c8d522a47","datavalue":{"value":{"amount":"+0.8706485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$CA74AD91-D842-4671-9395-90F4FE99E401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f876033a93fcff7f0467bd9bdc37afc736e2fbe4","datavalue":{"value":{"entity-type":"item","numeric-id":4526991,"id":"Q4526991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65252652a0be2dd2daf1a9a1a57b5e5e6c98500c","datavalue":{"value":{"amount":"+0.8688098","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$BF9E9952-C68A-4DEC-92BF-7D777A2F970C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ca7ecacfa33adbf6aba509fbb7e5c7503c6655f","datavalue":{"value":{"entity-type":"item","numeric-id":3391962,"id":"Q3391962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e68ad01871bf1ab3fbac27b939f8bc5eb367fa1","datavalue":{"value":{"amount":"+0.8677286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$7155DB44-6D45-4524-B855-B398CE087B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a210d365b245b900002b1b2fae6f733fef8ab2ed","datavalue":{"value":{"entity-type":"item","numeric-id":1754226,"id":"Q1754226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b81401aa639e7af5448e0625d5ecea3c3ab90b2","datavalue":{"value":{"amount":"+0.865142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$317E6A2C-5349-43B5-BBE0-E2BCA4C230F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20546fecc6c75bb7dcea80930d0beb6cfb629931","datavalue":{"value":{"entity-type":"item","numeric-id":1278421,"id":"Q1278421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"869946415ca9e888b220b9017a23e95daf72b1ab","datavalue":{"value":{"amount":"+0.86364186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$F0E5C366-C730-4268-BF6B-0F3BD39F70C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87ed11a6256f30233957d5494c824bd7c31a353a","datavalue":{"value":{"entity-type":"item","numeric-id":5479367,"id":"Q5479367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ee76a9ac1b512cba663c9830f0c16f40196cc9b","datavalue":{"value":{"amount":"+0.85953933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$1157E1EA-274C-4B0F-8340-406366C99E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f467e2eee9fe815f63821beaff44243cdcc579f5","datavalue":{"value":{"entity-type":"item","numeric-id":1016041,"id":"Q1016041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05903dcac1dc6a97c4c5daf8a78833a85f575c85","datavalue":{"value":{"amount":"+0.85306346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$A8D5B589-0E7D-4C39-85AD-E2809171EB45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38a857a8ac701d2c2f4a88589e8d09c0e9ae4a3f","datavalue":{"value":{"entity-type":"item","numeric-id":1400885,"id":"Q1400885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a24e26ba9b77d472390947b84e6472642b0fb35","datavalue":{"value":{"amount":"+0.8498495","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$ABC77837-9185-41CB-8FE8-EA822771E82E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53a0a80971093275171b34cb7e86f3abbdf988f2","datavalue":{"value":{"entity-type":"item","numeric-id":6168971,"id":"Q6168971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87eb4176997a794c81a2b7549246bd1fe634ace5","datavalue":{"value":{"amount":"+0.8439554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224275$4A3EE1C0-532B-4D7C-B2B7-3F639E445AB4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient approximation algorithm for the extension facility location problem on torus internetwork topology","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_approximation_algorithm_for_the_extension_facility_location_problem_on_torus_internetwork_topology"}}}}}