{"entities":{"Q1095035":{"pageid":1105787,"ns":120,"title":"Item:Q1095035","lastrevid":49115557,"modified":"2026-01-06T15:06:02Z","type":"item","id":"Q1095035","labels":{"en":{"language":"en","value":"A note on the average-case behavior of a simple differencing method for partitioning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4027178"}},"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":"Q1095035$1E77D0CA-41BA-4341-9777-DB6F75AB8FED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"930a8f80b298b8c8b9f7edd5d5f90afa094da053","datavalue":{"value":{"text":"A note on the average-case behavior of a simple differencing method for partitioning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095035$DBC63952-E673-4464-BA2C-0D652DCA1AD4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"63323dd74e7a1011aa28919b12095533276bae12","datavalue":{"value":"0631.90053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$541BFE0F-8E34-4FA2-9C62-B19226FA9BF7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d424c8573fc64e039d553763b35d5d28f3e5090","datavalue":{"value":"10.1016/0167-6377(87)90044-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$45A6CF78-43AA-43C6-B010-558E0370FE27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"43e40d96986a2628b2a68fc6d5e336c6d47dd78c","datavalue":{"value":{"entity-type":"item","numeric-id":221781,"id":"Q221781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$628A41BB-6FAF-4583-9483-364B817A90C8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$B522F958-D58C-4D64-A1A2-D839553B3CED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095035$B099BDEE-7C6A-4100-BAD7-3FB650836B01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f6e2366d0a64037b5c88bd8c9e4f5d7caaf80a8e","datavalue":{"value":"Given n positive values \\(x_ 1,x_ 2,...,x_ n\\), we wish to partition them into two subsets such that the difference between the sums of the subsets is minimized. \\textit{N. Karmarkar} and \\textit{R. M. Karp} [``The differencing method of set partitioning'', Report No.UCB/CSD 82/113, Computer Science Division (EECS), Unif. of California, Berkeley (1982)] have shown that a fairly complicated linear-time differencing algorithm achieves, for a broad class of probability distributions, a difference of \\(O(n^{-\\alpha \\log n})\\), for some \\(\\alpha >0\\), with probability approaching 1 as \\(n\\to \\infty\\). Their work left open the question of how two simple and more natural implementations of the algorithm behaved. In this paper, under the assumption that the input values are uniformly distributed, we show that one of these algorithms is not nearly so effective, confirming empirical observations of Karp.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095035$7F12BAD0-CAC3-484A-8B56-2FFBD36C7F44","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$ACCB5C27-63CF-4A28-AF4A-26C93EEA3A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$C237FC53-6EDF-4A1C-87C3-82A64DB97181","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15aed1e89c81a982df598763c767c85863e03ce7","datavalue":{"value":"4027178","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$D39E8856-2CA8-47D6-8ECB-CE4DF7B72C47","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0749026aa2353fabe10093f621f97d5d18f62e75","datavalue":{"value":"partition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095035$4A2BED22-E281-409C-92D4-9CB227A2579A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0b178a13c1500d511c7d237616ad0fe2ad28c03","datavalue":{"value":"average-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095035$CF982A3D-083D-463B-AAD6-10E7E9E88324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24a84be25e9c10d463deefddeffc8026de3632","datavalue":{"value":"differencing algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095035$C5C7DE56-95CA-45D1-A7DC-6C5ED3D4DA5E","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":"Q1095035$19120377-4F7B-4146-9233-893D8C04F5F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2d959a223131a8f7aac1389a55ef7c4844449db","datavalue":{"value":"https://doi.org/10.1016/0167-6377(87)90044-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095035$9889DD5A-2CE1-4CC1-AE77-BFD4A434A91B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"57d263171b7297e8e3c9383b7557090d6c61527a","datavalue":{"value":"W1990990015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095035$6A6AA825-81F7-44FC-9320-E426E5A3D2E6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e98909b5da236852b554e58fe752a1606791c68","datavalue":{"value":{"entity-type":"item","numeric-id":3779988,"id":"Q3779988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$A0918153-B4AE-46B7-8D37-FB8C78602016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"107b069bb038edf904c45e873f9f13e85d86ec07","datavalue":{"value":{"entity-type":"item","numeric-id":5512461,"id":"Q5512461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$731B6277-F515-4A2F-91AE-DC23971961B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$26343BF1-183C-4666-8F0B-124DF4D107BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd21fd2a8d3c703c5d4f35da5b44178f5802793b","datavalue":{"value":{"entity-type":"item","numeric-id":3750704,"id":"Q3750704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$8D546EA1-2163-40B9-B646-56D2DB71393A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095035$9C57284E-7CEC-4709-B5F1-36F1AA40775F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"452730210142030a7ba839f66138e3a8fbabd2c9","datavalue":{"value":{"entity-type":"item","numeric-id":4880878,"id":"Q4880878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca833c7d8e94f2e271787d5ea4459103e47b4e49","datavalue":{"value":{"amount":"+0.8550479412078857","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":"Q1095035$0B305AD3-15E4-4C82-8F3F-6CB9FA89C123","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":"15b699ace379e67379cd65aa9acf3ca8528be6b2","datavalue":{"value":{"amount":"+0.8416827321052551","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":"Q1095035$4EB364C1-DDDF-406F-BD13-FC840D6140DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78552687bcb0fda5c18e8b8d28ed7f7e718cdfc7","datavalue":{"value":{"entity-type":"item","numeric-id":2563882,"id":"Q2563882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"278dfbbd51e78777275419273446b1e6d3894fa5","datavalue":{"value":{"amount":"+0.8096035718917847","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":"Q1095035$981202B9-7113-4F1B-8224-399D374D18C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"effd492042408476f796f7aff1b6aa2dd06f9f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3750704,"id":"Q3750704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14c422e6ab28696ba35d2707701ed12075815af3","datavalue":{"value":{"amount":"+0.8041208386421204","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":"Q1095035$8E5EB2AE-A6A6-49A4-9462-C57ADE76AB1A","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":"58d5aa3e43bcc14c51581dc972e35899af8a642a","datavalue":{"value":{"amount":"+0.7965990304946899","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":"Q1095035$BCB9DE3A-73E5-429B-AE5E-572DB28628C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1095035","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1095035"}}}}}