{"entities":{"Q790814":{"pageid":792662,"ns":120,"title":"Item:Q790814","lastrevid":64494444,"modified":"2026-04-11T20:16:13Z","type":"item","id":"Q790814","labels":{"en":{"language":"en","value":"A performance guarantee for the greedy set-partitioning algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3849236"}},"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":"Q790814$A3CDC7DC-314A-4A58-940B-C2BC038BA25E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"140cbd0e5fb843fdf3029a4d09e5bea139751a93","datavalue":{"value":{"text":"A performance guarantee for the greedy set-partitioning algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790814$FB101414-87AA-47AD-9DEF-E76D0EC17880","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f64116175a7ad914a89fee52b88b3d0899397415","datavalue":{"value":"0535.05008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$A6CAE0AF-AD61-46C1-AE03-F01C910CD133","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b4da0c1155deb7e13fe6f85d75e8037926554f2","datavalue":{"value":"10.1007/BF00264618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$6738DE9F-43BB-4A53-ADC1-E82C5ADCD208","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790814$DC899E91-D154-4B51-9E30-BD1AEFB34E9B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q790814$FC579615-509A-496C-9F47-E2A98A1FB789","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5f063136738a85ae43f520ed715b702ef9dd65e","datavalue":{"value":"Let S be a set of positive numbers and m an integer not less than 2. The problem is to partition S into m subsets such that the ratio of the largest set to the smallest set is as small as possible. Let \\(\\rho_ g(S)\\) be the value of this ratio using the greedy or largest-first rule and \\(\\rho_ 0(S)\\) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that \\(\\rho_ g(S)/\\rho_ 0(S)\\leq 7/5,\\) and that this is a best possible bound for all m.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790814$46DB3F0D-24C7-46C1-9717-1C14B581141F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"58d33fcd5e5cb8a52812aa5e4a2f3f30b5cf0e30","datavalue":{"value":"05A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$B5358EFB-EADB-44FA-9F9D-98CA2DBA4A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$2C3CE5E7-9397-40E0-8CB5-A718AFFB3E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"679ddfba371ea56c373d120bb6ab79b1a5d003aa","datavalue":{"value":"11P81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$D3C9AF06-49F5-441E-BAE5-233E7C7566C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c52c731db8dbf83938062908d906ad695288a97b","datavalue":{"value":"3849236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$85C8A20E-72B3-4A05-901A-2BC2387FE61B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd67ce27188c75299c9b3796e4173a4e7f538aec","datavalue":{"value":"set-partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q790814$0166B995-64B7-4413-BFC1-276ED72D9A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d21e0b9a7c824e408ff49cf6a54144c47575977","datavalue":{"value":"subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q790814$5971A141-ED56-48CA-B39A-98ED6B084850","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6f02c949a7cbb2eccad0504dce0699ace40f95e","datavalue":{"value":{"entity-type":"item","numeric-id":948705,"id":"Q948705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790814$F8ECFB34-DC66-4CCF-B7C9-A224EBCD5BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d288423df0deba1f237a49670693efc500bb8d57","datavalue":{"value":{"entity-type":"item","numeric-id":293396,"id":"Q293396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790814$EAE3E1E7-AAE3-49E6-8AF4-34737D577A88","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":"Q790814$B3D7EDBA-1584-44FB-BD2D-E1EA2DB03AE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02ff8f5db2b9b0945338610e393814ddd089c48b","datavalue":{"value":"https://doi.org/10.1007/bf00264618","type":"string"},"datatype":"url"},"type":"statement","id":"Q790814$AB0EAC61-264C-43D3-9AB3-631CA97EC94D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a36d12bae13eca736c9e05b983a02704cdc089f","datavalue":{"value":"W1964048951","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790814$E474E71B-57EE-44BE-BB9B-36353B474B15","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b68b5e336f90377471197734dab072b91276a22a","datavalue":{"value":{"entity-type":"item","numeric-id":4254655,"id":"Q4254655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"518b3cc2ed577c4dde492a7e912c25256e35e2d7","datavalue":{"value":{"amount":"+0.8218950033187866","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":"Q790814$131B2635-6C4D-4142-BD7B-A94A68868068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e19b3d9ea5c18baacb4d9d58e545f3aeb072f5b","datavalue":{"value":{"entity-type":"item","numeric-id":435724,"id":"Q435724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"518b3cc2ed577c4dde492a7e912c25256e35e2d7","datavalue":{"value":{"amount":"+0.8218950033187866","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":"Q790814$09AE51AF-D085-49C7-83D4-3A72630AF1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8a1574f45764b1403f1eec1e1d0f7e5bfc18eb8","datavalue":{"value":{"entity-type":"item","numeric-id":4418683,"id":"Q4418683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0eb8bbfe9dbfa2ca85b1405927389c816be0e72","datavalue":{"value":{"amount":"+0.8144965767860413","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":"Q790814$2799FB7F-F3BC-4E13-ADF2-D7BCAC150A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328213bb9d103d715419d500ee96c875328eafa1","datavalue":{"value":{"entity-type":"item","numeric-id":1572977,"id":"Q1572977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e9dcb41a1ace1c788296100e21f03e1e9bebe6c","datavalue":{"value":{"amount":"+0.8010155558586121","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":"Q790814$609EFE78-92EF-48D7-9477-0E82E9556197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"021c0d77ad221b0c12f2a655684ae8e74a4be63c","datavalue":{"value":{"entity-type":"item","numeric-id":4374000,"id":"Q4374000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e9dcb41a1ace1c788296100e21f03e1e9bebe6c","datavalue":{"value":{"amount":"+0.8010155558586121","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":"Q790814$93CD1954-ACC4-4D60-B489-FC6E6F2CC502","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A performance guarantee for the greedy set-partitioning algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_performance_guarantee_for_the_greedy_set-partitioning_algorithm"}}}}}