{"entities":{"Q5958140":{"pageid":8134942,"ns":120,"title":"Item:Q5958140","lastrevid":47754379,"modified":"2026-01-02T14:51:34Z","type":"item","id":"Q5958140","labels":{"en":{"language":"en","value":"Approximation algorithms for channel assignment with constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715106"}},"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":"Q5958140$1D53B634-73EB-4CC9-8907-D96790E3AD18","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"412222db60be5724657c0ae3f4babf463ceab401","datavalue":{"value":{"text":"Approximation algorithms for channel assignment with constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958140$060CE46C-70E6-4224-B4FB-2780AB36BAF5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a9930b6f74b9a4f71f9e3aaf874eae842b34f146","datavalue":{"value":"0983.68139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958140$86DA3A76-BC4C-4080-BDE8-2038A9B427A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69e59cd625bddf4c0ea13fe11bd2453fc0b23d59","datavalue":{"value":"10.1016/S0304-3975(00)00388-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958140$4B8A4AFD-C81A-4A34-946F-848E3F355C1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d78501335861375842f274f1c1e5006caa3d42c","datavalue":{"value":{"entity-type":"item","numeric-id":1344238,"id":"Q1344238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$4E792C13-2ACC-4F92-A3AE-8B4435A7458D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b6527a4b5d6e9c5f962b981734b69d02b85932","datavalue":{"value":{"entity-type":"item","numeric-id":385053,"id":"Q385053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$9BBA9A62-6825-4B06-BD03-BB6A1B42E9C1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$DFE2FCA8-8908-462E-9855-3E12499D0BD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-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":"Q5958140$5E0D2B02-917F-4217-8872-390718DC9E6E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9efce4231e4a44a1ebd7a0f1a01b5c144ef51f8","datavalue":{"value":"Cellular networks are generally modeled as node-weighted graphs, where the nodes represent cells and the edges represent the possibility of radio interference. An algorithm for the channel assignment problem must assign as many channels as the weight indicates to every node, such that any two channels assigned to the same node satisfy the co-site constraint, and any two channels assigned to adjacent nodes satisfy the inter-site constraint. We describe several approximation algorithms for channel assignment with arbitrary co-site and inter-site constraints for odd cycles and the so-called hexagon graphs that are often used to model cellular networks. The algorithms given for odd cycles are optimal for some values of constraints, and have performance ratio at most \\(1+1/(n-1)\\) for all other cases, where \\(n\\) is the length of the cycle. Our main result is an algorithm of performance ratio at most \\(\\frac 43+\\frac{1}{100}\\) for hexagon graphs with arbitrary co-site and inter-site constraints.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958140$45E60F33-011A-473A-B86B-66FC35509781","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958140$3C4710E4-1025-4D70-A164-C0D364BB6BFF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"109761f5ea1beb745278a68aa2f1e1b6305fb9e0","datavalue":{"value":"1715106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958140$19A5EAFB-3D8C-4074-A32F-1E78C21C5DAE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42694330e261e49fc9472c2ab1c262aff0f6a9d4","datavalue":{"value":"frequency assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958140$EF05A7F8-4736-4223-84AA-B57C53C0671B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958140$6BE0B882-3497-4069-A3CC-E55530AA8E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a550ae3d7cc50aae4b49fcc68414383615b4b0ef","datavalue":{"value":"radio colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958140$38C062BA-29AB-4E0E-995C-3BB1F61AD20E","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":"Q5958140$D5E03F14-B2BB-4A45-84C0-6C721CBB24F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$3F2B5CF6-A440-495D-815F-3B6A6C69FD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b7ccdea7fc17f46ecb895b5fe84e80a9180969e","datavalue":{"value":{"entity-type":"item","numeric-id":1586761,"id":"Q1586761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$2AE25218-CFBB-4067-9456-9C31F7A55DEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e012a7900e34a033a7dd5faca89c09b3011b98d1","datavalue":{"value":{"entity-type":"item","numeric-id":1586355,"id":"Q1586355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$A781B472-8782-4CC5-9551-EECB0119CBF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1f4f53bc96099d0f0fdffcef8de9fae7368b09c","datavalue":{"value":{"entity-type":"item","numeric-id":4519133,"id":"Q4519133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$3586971C-CD66-4EB3-B355-08F27ED9A242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12f87d9c8b87d02229fb8a4156894baaafa63bc5","datavalue":{"value":{"entity-type":"item","numeric-id":1348916,"id":"Q1348916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$4718A74C-BD05-4216-B705-2EC18F493B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d10f091cfa5930ab05263cb0f870bca60377febb","datavalue":{"value":{"entity-type":"item","numeric-id":293383,"id":"Q293383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958140$7C33DD58-729E-4B72-B3AA-F1B44B31AF66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a43917d5256343cd8b81b0ba47f1f3966e9f03a","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(00)00388-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q5958140$E0D4F88A-5C18-46AC-B33A-D635764F9452","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"246a99fcaf85d5a0c6dcacd340c8f18f05363b02","datavalue":{"value":"W2081777937","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958140$6D9FB03E-34DC-4699-AD50-2816DDCBF6C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efdb771128ee931266b8930e145b19bfe030d6ed","datavalue":{"value":{"entity-type":"item","numeric-id":4511237,"id":"Q4511237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a94eaa015b8236d012739d62fd9e9ccec844bd07","datavalue":{"value":{"amount":"+0.9971379041671752","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958140$E6B5DDFC-E441-4CED-815E-91503AA65199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2cbe5bfb2c6ab43b0ad91cf81bd03fb7fc539b9","datavalue":{"value":{"entity-type":"item","numeric-id":5434411,"id":"Q5434411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a94eaa015b8236d012739d62fd9e9ccec844bd07","datavalue":{"value":{"amount":"+0.9971379041671752","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958140$A2D3B266-2B10-4278-B223-850A19F75932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e93c643e036002f2bf9537ab073df68515a86f57","datavalue":{"value":{"entity-type":"item","numeric-id":3171169,"id":"Q3171169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"602cee17ff8ddd04447f87046eb6ed3cfb374050","datavalue":{"value":{"amount":"+0.927454710006714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958140$A5741FD0-5A42-422B-90C7-49DA96BDA8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be626b840db0f03f0307dd16259b3c2db4a88115","datavalue":{"value":{"entity-type":"item","numeric-id":3974882,"id":"Q3974882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd3372f95b7776db06978ea63204210b52bcda64","datavalue":{"value":{"amount":"+0.8903684020042419","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958140$E7ED7D66-B11E-4F4B-A743-52E95477E731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f9511611e586790b66f8b0a3a9661a009b55ebd","datavalue":{"value":{"entity-type":"item","numeric-id":5930155,"id":"Q5930155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd3372f95b7776db06978ea63204210b52bcda64","datavalue":{"value":{"amount":"+0.8903684020042419","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958140$11A01BB8-CB61-42CB-B740-8F3D94820FA3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958140","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958140"}}}}}