{"entities":{"Q916568":{"pageid":918416,"ns":120,"title":"Item:Q916568","lastrevid":49394533,"modified":"2026-01-07T02:17:39Z","type":"item","id":"Q916568","labels":{"en":{"language":"en","value":"k-sum optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4154220"}},"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":"Q916568$543FED1D-C98F-4EB2-8F30-47DED399C79B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d78987e1926869bb3739eed544e6a7fd38ccc47","datavalue":{"value":{"text":"k-sum optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q916568$4E254389-BBC1-4B67-AE6A-875F5F6955EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32987ddbe84fdf7ea8ff6aed5e350bad1a119a2f","datavalue":{"value":"0703.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$714ED1F2-1F86-4C36-81FB-4A4B42CCCCF7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c252aad3b98b572d8a183a46705553e741aa3821","datavalue":{"value":"10.1016/0167-6377(90)90051-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$8B5416CE-AB84-4522-9E7E-0F3C5E1D197C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cafcd604aa5a58f9578b2ea045ac63c0c47fe68","datavalue":{"value":{"entity-type":"item","numeric-id":167967,"id":"Q167967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$C7697F5F-B8E3-43A9-8CB6-1EF27A6152F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3145210ff03b7e6872f84577842c5a1fe41816db","datavalue":{"value":{"entity-type":"item","numeric-id":293329,"id":"Q293329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$603E96F8-9E9C-46F4-88C1-6B11ECD3E63A","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":"Q916568$5E9081BD-F9A9-41B9-AED8-19A976EF411A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q916568$39295A9A-1048-43C7-A0FD-DDA641628DC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c795d1000e61ced28e75dc58a2b824b4bff306f","datavalue":{"value":"Given a family F of subsets of a finite set, where each subset S is of cardinality n and a weight is associated to each element of S, the k-sum optimization problem (denoted by SUM(k)) is to find an S such that the sum of k maximal weights associated with S is minimized. In an equivalent manner k-sum deviation problems are defined. k-sum optimization problems can be solved efficiently if the corresponding n-sum problems are efficiently solvable. An alternative characterization of matroids is given: F is the base system of a matroid if and only if every optimal solution of SUM(n) is also an optimal solution of SUM(1) for arbitrary weights. As a special case the k-sum spanning tree problem is solved by a decomposition algorithm. Finally k-sum deviation problems are shown to be solvable efficiently whenever a related minsum problem is efficiently solvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q916568$B1CEE4D4-1182-44D2-AA22-98A183743DC9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$AD943710-1360-4A05-9DD0-BDEC2B344725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$1764D3F3-B6BA-4671-8518-D93B533EB848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$07BF936A-9F31-44CA-BBD1-24A908D1B7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$ECB4B900-24FA-4F68-B5BA-D59BA2D73D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fcde6944a05b42fc9b58f696b7d5b9f7be8e3c86","datavalue":{"value":"49M27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$59CC0C74-5E74-45D4-BEBF-B9D1A2774156","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fb057630af1ccc68a8f2d90bacbfd53938c69220","datavalue":{"value":"4154220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$DF7E3BD1-9B5C-4696-AC0D-39367B3C1C6B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd4350c1c19f9e0e00c6dfa3ce19b6ed35c31ccf","datavalue":{"value":"k-sum optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q916568$3C777E76-E8DD-4C8E-829D-8CAAC933E156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6540ac1ac89715e9d657e8eb8c438e69dc61426c","datavalue":{"value":"k-sum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q916568$1317CDE1-B35C-466F-8586-9985BAEFF54F","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":"Q916568$559FEB68-B00D-46AB-896C-154A86546B59","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7fa3106ee8abe2a0d840ab879445b5796eff8aa5","datavalue":{"value":"https://doi.org/10.1016/0167-6377(90)90051-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q916568$59AA3311-BC40-4244-8B05-DCD00CF05C7C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bbcc93ad802934781945c739c9f7f28679027326","datavalue":{"value":"W2012865538","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916568$F8F0D143-333C-4846-BD60-52DC7B1FBFB4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67ea5acabf8dd4b36da5d5390eb1b7f044530ad","datavalue":{"value":{"entity-type":"item","numeric-id":3698817,"id":"Q3698817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$F417A840-D5E1-4B0B-B454-0BBEB3462770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5da7b5501ac2861620b4c30b491c98420835dec","datavalue":{"value":{"entity-type":"item","numeric-id":800815,"id":"Q800815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$711A131A-3276-4911-BE40-C500050CA100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffe42ca938ed45695f535521b2107403cef25695","datavalue":{"value":{"entity-type":"item","numeric-id":1244239,"id":"Q1244239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$864EF52D-3AA0-4D3B-B898-752AD2F6B4E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d601b5a73aa3f981ed43e68477a6afb0b2f45837","datavalue":{"value":{"entity-type":"item","numeric-id":1086246,"id":"Q1086246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$1A040128-C8C0-49CE-B5C5-8725BA93D2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d02bc3c5109e4c30f9db7cc38c158f9b0be1f06e","datavalue":{"value":{"entity-type":"item","numeric-id":3953561,"id":"Q3953561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$DDF55E8E-F6A7-4A04-93D0-F9CEF212B268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96efbc4f6407087bb1c5df0896c491c38d836ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1104246,"id":"Q1104246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$A9F44CF1-A6EC-4AAB-8391-FFA26A91CA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$A0CF3EBA-456A-49CA-9413-6DA70E9EB028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b41ba5dbbeebdc581ab76ad621e30e64cd67c78","datavalue":{"value":{"entity-type":"item","numeric-id":760338,"id":"Q760338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$76E84A4D-94D8-4A89-B8D5-B668C40AAB65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$1F8C9997-5344-4142-B1CF-B625BC144F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b351f9c0e46814651838c848c272e0f365b7d4e6","datavalue":{"value":{"entity-type":"item","numeric-id":3859785,"id":"Q3859785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$6ECD7B30-EE7C-44EB-BF16-46BAB0D02243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916568$DB3AF015-2ABB-420E-8F23-46017037D5A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a498df7ad2a02633a73326df3e700f0d5d3c9eac","datavalue":{"value":{"entity-type":"item","numeric-id":1919195,"id":"Q1919195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cc90e2cd17fa50d2c93c138d5a66130b2a8b78c","datavalue":{"value":{"amount":"+0.8223176002502441","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":"Q916568$8A1F375B-EED9-464C-AC00-332C88D94F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"995318aa846de65577524cde00fc0d9229034d09","datavalue":{"value":{"entity-type":"item","numeric-id":3342227,"id":"Q3342227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"591c9779bc18bb184590f77127117c68d7295a7a","datavalue":{"value":{"amount":"+0.7937328219413757","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":"Q916568$B01DB0CA-CB6E-4C13-B8C8-E0530F091A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc359ff2d448b08fe3da2b139b842d4fcba65f79","datavalue":{"value":{"entity-type":"item","numeric-id":4323418,"id":"Q4323418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52ee91fbba74d895c5da18efcf6d3cd92042486c","datavalue":{"value":{"amount":"+0.7853924632072449","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":"Q916568$96348F69-1911-49DD-BA97-CC34F53068D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87a138a5c74c22b23747c161a311533f91e8d246","datavalue":{"value":{"entity-type":"item","numeric-id":1824562,"id":"Q1824562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca515d0bb0653feef5ebf7eb70b6e2f119fac56c","datavalue":{"value":{"amount":"+0.780583381652832","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":"Q916568$B1C386C2-617C-439C-893B-75470F71E662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"820a427694100089ab966b0048f8d863ab38b604","datavalue":{"value":{"entity-type":"item","numeric-id":1675256,"id":"Q1675256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ac9bf0a56f00938b42c776497931ef2445fbc20","datavalue":{"value":{"amount":"+0.7798727750778198","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":"Q916568$2CE67FC2-49E3-49A4-8AE1-852EE1F4FFF6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:916568","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:916568"}}}}}