{"entities":{"Q1884770":{"pageid":1895512,"ns":120,"title":"Item:Q1884770","lastrevid":73703991,"modified":"2026-04-14T16:58:32Z","type":"item","id":"Q1884770","labels":{"en":{"language":"en","value":"Primal-dual algorithms for connected facility location problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2113912"}},"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":"Q1884770$6A56EEF3-6873-4C3D-A380-DABBFA74F4FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80e3186f9c6e62f32b07339392063210851436df","datavalue":{"value":{"text":"Primal-dual algorithms for connected facility location problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1884770$A2B90790-BC51-40B3-9D5B-C8ED03820A53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6d3d2235b0075bb46907f3e99a6e5669be6b95c","datavalue":{"value":"1108.90026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$D4327E2D-252B-4C91-9F79-4E579332C0EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"020422b815b783ac8834fc5d33733a6d106c3a8b","datavalue":{"value":{"entity-type":"item","numeric-id":662295,"id":"Q662295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884770$815FF8A5-9614-4104-B36C-8C03C8E31790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ecd9190cba002a020883782f1e22c14702b8d656","datavalue":{"value":{"entity-type":"item","numeric-id":486975,"id":"Q486975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884770$C975704C-B300-43F7-B9D7-573DDA8DB6C4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884770$3E147C9D-E6C4-4230-8B1D-08C8115FD737","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"66f51029b9e38c366fbfa63f3a7b20beee0c294d","datavalue":{"value":{"time":"+2004-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1884770$4EFD7A0C-C91E-4EBC-8759-2FE13ED2FB77","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"236f3d4c7c45211f5f7488a56b7386238871f40a","datavalue":{"value":"A Connected Facility Location problem (ConFL) generalizes FL-problems by additionally requiring the connectivity of the open facilities by a Steiner tree \\(T\\) yielding an extra cost of \\(M\\times\\text{cost}(T)\\); here \\(M\\) is an external factor due to the specific requirements for Steiner edges (f.e. connecting hubs).  The authors propose constant factor approximation algorithms based on the primal-dual scheme, where simultaneously an integer primal solution and a solution of the dual of its linear programming relaxation are determined. In a first phase it is decided which facilities to open (by aggregating at least \\(M\\) demand) and which part of the cost should incurred to the Steiner tree portion of the dual solution.  The second phase constructs a Steiner tree or an approximate one in polynomial time. Altogether, the paper shows certain constant factor approximations for ConFL as well as for the connected \\(k\\)-median problem (ConFL, where at most \\(k\\) facilities are allowed to open) and for special cases (f.e. \\(M= 1\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$5C39EB82-0991-468C-AD63-FDECA60940E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884770$F862D83F-7174-456E-B02D-C458324F74A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$CE691028-0D54-4182-8B4B-59361FABC7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$F3C95160-BB84-48B6-8499-521C8044D8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$EDA034EB-DE68-431F-AC20-738D65D48E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$7607796D-8FF3-4079-A9E9-FE2FC15CCA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$BA4920C8-7528-4A4B-839A-46C6560CA35F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0a9259451471279a67141b1dcf28d549b2ca8b93","datavalue":{"value":"2113912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$FF890AF9-4709-4B80-9C25-BF731756107F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbff35acdd31439d13dd3892bdda5725c18fc300","datavalue":{"value":"Approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$526397E5-E304-4D1A-A7A7-92DB8AE217A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa6cafe4addf88f196f23b597df00edf222200b6","datavalue":{"value":"Primal-dual algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$F4BADDF8-5A9B-4A48-B8F3-7640C78516C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e34785d8afd5440afc3f5563370c11ac3fe5622","datavalue":{"value":"Facility location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$BEF09F0F-F23E-4CAD-ACB7-E339D62D5D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c27f95e6c885729b58d1ea8f1416d57edfc6b2b","datavalue":{"value":"Connected facility location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$91D33DED-D445-47DB-8E27-0C0ADC10D831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a9fa2bccaf30a54211b58d741df01c436111be0","datavalue":{"value":"Steiner trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884770$EB48ECBC-6A03-4A8A-A4E7-D1DFBA8A7A74","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":"Q1884770$7DA0B9F0-8733-4465-9E8C-B640A7FFA818","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"204a1adcccc2b3468ad7bd4f3ab3b8b13f72448b","datavalue":{"value":"https://doi.org/10.1007/s00453-004-1112-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1884770$69AE4CAD-7E44-4538-A804-DC8E08DC2305","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"abd3b28538787c6714876d19d467543650ac37ae","datavalue":{"value":"W2147879413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$AE225082-A71A-4AA0-B4E2-047E0E38F0B3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b19a888a0adc2defa5e9bbc110eb316e899c0d4e","datavalue":{"value":"10.1007/S00453-004-1112-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884770$AC1723B7-AC10-46E9-83BA-FB93754230BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b0e89935ebc2acd36fc6ec5e6b44aba2c2775e","datavalue":{"value":{"entity-type":"item","numeric-id":4411292,"id":"Q4411292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$E83DF38E-2A4A-44AF-8C13-BABEA275B128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5c095cadfacf881639e7b47a6580552a6c0833","datavalue":{"value":{"entity-type":"item","numeric-id":5505665,"id":"Q5505665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d306707129029ddb3bf8fb0bc1b06c9fc8cdc311","datavalue":{"value":{"amount":"+0.9583174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$88D59DB1-9699-48C1-B19C-AB4437DAEAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33852cda7045bb53bcce5daa5688208d860c69ae","datavalue":{"value":{"entity-type":"item","numeric-id":1041431,"id":"Q1041431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6dd01d50f8c89c0d42a45c28cf4c1d8e3e44896","datavalue":{"value":{"amount":"+0.92643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$F8A86908-89EA-432E-9DBE-9914FFE9F44C","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":"e8e7ea3ade63e0d8618ca8f7cc9f23f2fe630330","datavalue":{"value":{"amount":"+0.92586714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$6AADD438-E5D8-42DF-9DB9-5AA121ED912A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56eaca9ef2d12b4328dec6cff3694af7ad6d1ffb","datavalue":{"value":{"entity-type":"item","numeric-id":2429335,"id":"Q2429335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52b46ddd62598b38481d3d9966b2327cb35bfa94","datavalue":{"value":{"amount":"+0.90764076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$FBC33590-70C2-4EEF-8CF0-20B47A6115AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d6cf368435cbc0dd825dd083415f45ec6d07c7f","datavalue":{"value":{"entity-type":"item","numeric-id":2899090,"id":"Q2899090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c7b1b1e1add9d3769a4591d9b50d603b1d2af23","datavalue":{"value":{"amount":"+0.90155005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$6A1A371D-4CF7-4678-A211-247D1DD89525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be31ca628de429e5e9fb572d0f953b034a9459e","datavalue":{"value":{"entity-type":"item","numeric-id":3009767,"id":"Q3009767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbe730f0fa7f69c245cb3db522c80379f010a38f","datavalue":{"value":{"amount":"+0.8987992","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$D2FD77FE-A9CB-4E49-9D38-EE5270E16F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ba6e91c5aea1d2b4401c6a25b73bb492208ecf7","datavalue":{"value":{"entity-type":"item","numeric-id":3220311,"id":"Q3220311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8d4810f0aaaf660e3cf1fc2254b126f2c1828ed","datavalue":{"value":{"amount":"+0.89571047","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$9627B61C-98D0-4408-ACEE-DA2150A3F7A6","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":"420eda0b697669b5ac7a5f532fd7a2e394b2bdd3","datavalue":{"value":{"amount":"+0.89532655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$3A315881-8BD2-4F0D-B1A0-50DE351513AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1aadbaa4bdcc44f852dccfb60e1cf49dc39cad7","datavalue":{"value":{"entity-type":"item","numeric-id":2695316,"id":"Q2695316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"152bba8bfa7fd3525c3825607bed80d5a172b6b8","datavalue":{"value":{"amount":"+0.89303637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884770$0172196D-183C-469D-A33A-F79C5AC6D2F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Primal-dual algorithms for connected facility location problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Primal-dual_algorithms_for_connected_facility_location_problems"}}}}}