{"entities":{"Q662296":{"pageid":664145,"ns":120,"title":"Item:Q662296","lastrevid":51423131,"modified":"2026-01-18T04:22:56Z","type":"item","id":"Q662296","labels":{"en":{"language":"en","value":"LP-based approximation algorithms for capacitated facility location"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6008678"}},"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":"Q662296$29E4315D-DB59-4159-8A17-DAF0A5C86A9D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7ec25bb22fe049b4d1d235fbfe00c51d1fb3386c","datavalue":{"value":{"text":"LP-based approximation algorithms for capacitated facility location","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q662296$485B6320-96DB-4B93-8249-11958EB1BA93","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba852f33f6d4947e54e2bb6ea1f3a18e77240fa0","datavalue":{"value":"1247.90055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$F30836C8-E004-43F6-AD72-451F9A4EE178","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"799bb163aea1fe2454813b84a286137285d0901f","datavalue":{"value":{"entity-type":"item","numeric-id":304236,"id":"Q304236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$5198C21F-C0CE-46A5-84E2-8E3AF1536F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11c1f1f9079d02ebeb6b8cf94e1bc627bd0842c1","datavalue":{"value":{"entity-type":"item","numeric-id":304237,"id":"Q304237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$78874053-FC86-4A93-BA66-798FD86063E0","rank":"normal"},{"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":"Q662296$C8DF67E3-9D88-4484-985F-727B78720ED7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$155249E5-6E57-4A65-A5E4-AEA0146141B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"164a811b4fdf46ae7f08d0247338084cafa3851b","datavalue":{"value":{"time":"+2012-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q662296$515E8A29-1942-4A4C-B4C7-18C9B38088BE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eba34fbaee8fd13f9726a5d9f759f3f34643e062","datavalue":{"value":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.1797","type":"string"},"datatype":"url"},"type":"statement","id":"Q662296$944ACABB-C43D-4115-AD97-C0D889186B63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aeba6ec666f77b12d947ef0053c45e34b0a84591","datavalue":{"value":"In this paper, the authors describe an LP-based approximation algorithms in the case of the capacitated facility location problem with hard capacities.  The novel described approximation algorithms, 5-approximation algorithm, is the first LP-based approximation algorithm for the capacitated facility location problem with hard capacities. The algorithm is obtained for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. The main idea was to view the optimal primal solution as a bipartite graph and then this was used to construct a partition of the demand and facilities into clusters: each cluster is centered at a client, and the neighbors of this client contained in the cluster are opened (in the fractional solution) in total at least 1/2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q662296$B35570A2-8501-421F-977E-825B97485214","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"810d660658648f9bc3138c1cd0aba8029bb9050c","datavalue":{"value":"90B06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$BE5E0C3B-A194-4F98-A76F-53744DEE074C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$68D5666B-C713-45A6-B056-897E3B3B24B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$149B1A5F-A42C-4231-9B22-6F25F7BB7E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$51A656A9-980D-456D-A3ED-5A61AD26C753","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6349d3d05f5dcc974caaaf45dbe8c6fe10c890fe","datavalue":{"value":"6008678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$A1F646F6-4CF6-4930-9012-EFD77C44C834","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8492ebd27dff02e07dc0f256015efe5a34cd3d0","datavalue":{"value":"capacitated facility location problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q662296$BDF3653D-4584-4615-8FFA-F1665E46F286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e0b408cfdaa4c4261e74ee9821e29dcd52b6a9d","datavalue":{"value":"LP-based approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q662296$7024A382-C0AB-424B-9F1A-C99800223D92","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b2e2936f14ed4ac57a25cb265a3d2d00acb32d2f","datavalue":{"value":{"entity-type":"item","numeric-id":455035,"id":"Q455035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$107907B2-F9C5-47EE-92AD-8F19A1C56D71","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":"Q662296$03DECDFF-1F86-4262-8E73-F50F69A2245C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfb2b6c9858ea0b7451100a2faab1388dc4739d5","datavalue":{"value":"W2028549267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$44F7FED1-C0D2-4851-8E38-CEFB7D920F3D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1ffabe25b98047738f1187ad0b38bfd0a691a6a","datavalue":{"value":{"entity-type":"item","numeric-id":1290613,"id":"Q1290613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$58D37CE7-4887-46C3-B545-144CB2AD073C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf3bec8ad092b15395c118feb8cb5e57159eeb6","datavalue":{"value":{"entity-type":"item","numeric-id":3503854,"id":"Q3503854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$21E961B6-FA41-45F1-A70F-301282531E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f4dc4c256137d16b59ce1cbaa41b7b76527b529","datavalue":{"value":{"entity-type":"item","numeric-id":4952606,"id":"Q4952606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$553C06DE-FB02-4FE7-84CB-831959F0571E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80263c22192e6ca2e88a5fea935efe00448d33d8","datavalue":{"value":{"entity-type":"item","numeric-id":1771310,"id":"Q1771310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$317E8ACA-E129-4035-A04C-47657424AA0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20d09513baf32113955ba3ecf79c8e2d6ab34f2","datavalue":{"value":{"entity-type":"item","numeric-id":3512428,"id":"Q3512428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$C363DB99-2FDD-4E2B-A84D-5A7C77AA85A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b15467bfbb88b44b0b8bd274e6db34bcdf96502","datavalue":{"value":{"entity-type":"item","numeric-id":4512576,"id":"Q4512576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$C4A8D684-1259-4911-AA9B-70A87397E4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b4dd68c05e6fca782d66026f384902a6fd6755","datavalue":{"value":{"entity-type":"item","numeric-id":3168976,"id":"Q3168976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$4C5AA776-1D2D-4AC6-8BAF-A09379BE42E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dff0087fd77030ff9e1d8191e386d6a2c9fcb71","datavalue":{"value":{"entity-type":"item","numeric-id":5712454,"id":"Q5712454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$CC287CEC-57CB-4D96-9CCB-1461F4CA4AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb2fcce01afff6aecab2a5df3035400002516fd","datavalue":{"value":{"entity-type":"item","numeric-id":5897264,"id":"Q5897264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$8FED7B24-FCB3-420D-B93A-DEFCAFA55226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6c62b10980d2754a06713497a071907d9ad826f","datavalue":{"value":{"entity-type":"item","numeric-id":3434992,"id":"Q3434992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$2FFFC557-5D20-44BF-8DD3-E35172E9B1AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64aeaa85587aeb8505e54a77d579017e954e0b6b","datavalue":{"value":{"entity-type":"item","numeric-id":3703656,"id":"Q3703656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$D3349424-4336-422C-AD85-F1F4CC8DEA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eedd0343e86c2dac433f3c49b193aa0ed978fb6c","datavalue":{"value":{"entity-type":"item","numeric-id":2753723,"id":"Q2753723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$6D600A61-D9DE-4539-8F68-EC5877CDCF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5d8710e77e3a71c4bff4c04013e9d4342dabb0a","datavalue":{"value":{"entity-type":"item","numeric-id":1319018,"id":"Q1319018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$AF96D3D4-606F-4BDE-8060-7899FB0F271A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61a00527f401c012cfdc93ea2fe726513b73b3a","datavalue":{"value":{"entity-type":"item","numeric-id":4526991,"id":"Q4526991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$B05AAB1F-1130-4CC6-8203-CEFE8E09D879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a193940aa550b8ae916ae07a33e75547c27a70d6","datavalue":{"value":{"entity-type":"item","numeric-id":4471365,"id":"Q4471365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$D1086677-BC9D-4190-904E-D276FAE31F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15e6bad7997a61592c2da611d6765b824422cddc","datavalue":{"value":{"entity-type":"item","numeric-id":5704227,"id":"Q5704227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q662296$D99BEF25-3AE7-4DD8-A065-CD090ACA989D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2018869b87fae448680767737c8729cc8854d7d9","datavalue":{"value":"10.1007/S10107-010-0380-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q662296$CE923DCB-D43C-4F21-8F44-C6F9F77CACD5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b56abbe2522c937717c96a1fe81b4074d9b280b","datavalue":{"value":{"entity-type":"item","numeric-id":5712454,"id":"Q5712454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be869a4e1234e75a5ca9c295d357c33f526380c1","datavalue":{"value":{"amount":"+0.9182980060577391","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":"Q662296$687A5385-E2A2-4A0D-8D3B-9A8B4408F153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81b0652db5679056939c3c541abc437969714fec","datavalue":{"value":{"entity-type":"item","numeric-id":2968155,"id":"Q2968155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8beac0c6b07e345eab926e0778cf48d094257fb6","datavalue":{"value":{"amount":"+0.906891942024231","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":"Q662296$0A17CA35-E633-42D2-B1A8-B8A8F7DDC56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16ddcc7f5a1fce948a4e9335d32223e69ca19239","datavalue":{"value":{"entity-type":"item","numeric-id":2172086,"id":"Q2172086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cabcffb414e23a9a7fdad95e22b06d2ba52daeab","datavalue":{"value":{"amount":"+0.8731467723846436","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":"Q662296$305B5ED7-F2C2-44F1-BAA1-9D3430F7C274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6465a2cc2510f91114b1b017e444c91e4c6afa1b","datavalue":{"value":{"entity-type":"item","numeric-id":5900928,"id":"Q5900928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a28fa8cdde60ec36543a8c6a0881da3596746e","datavalue":{"value":{"amount":"+0.8424469232559204","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":"Q662296$9C84C2A0-F957-41F7-853E-3C0ADEC6406D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4583a80cfaae35278273b05796e24992252de036","datavalue":{"value":{"entity-type":"item","numeric-id":2630091,"id":"Q2630091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"379583165c8b17a4ad293ac293f58d201c7be66a","datavalue":{"value":{"amount":"+0.8350627422332764","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":"Q662296$5F10C5C5-4A50-4923-B5B9-F907EF490875","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:662296","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:662296"}}}}}