{"entities":{"Q2366610":{"pageid":2377353,"ns":120,"title":"Item:Q2366610","lastrevid":46345680,"modified":"2025-12-24T14:57:18Z","type":"item","id":"Q2366610","labels":{"en":{"language":"en","value":"The partition problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 227183"}},"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":"Q2366610$02E89B7B-F046-4198-B28A-335249416636","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca613b11b04d8f47aa40958d75dd1e28a0581add","datavalue":{"value":{"text":"The partition problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366610$B8246ADF-9668-4782-9FAE-2E95BEDA7687","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f149083fd9804cbe526f7176e21c833aa4a277d","datavalue":{"value":"0774.90082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$5EEE49AF-64C6-4242-A270-7170D813C93F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"508859f803e96c231697c7918a4421bc86b625be","datavalue":{"value":"10.1007/BF01581239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$F894A6BB-C19D-4074-9D67-80580D59D10D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$1CC9ECCE-FBB7-4662-BCEF-F5234C7A6425","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":"Q2366610$F48FEFCC-5A9B-4DA8-94D0-C957D3F73E5B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366610$0C951170-7E73-43E9-AB97-4AF8CB59D000","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c64249eb13778229751f3d48bf6207e24d3a9ac","datavalue":{"value":"The authors are dealing with two graph partitioning problems:   \\(\\text{GPP1}(k)\\): partition the node set \\(V\\) of a given graph \\(G=(V,E)\\) - - with edge weights \\(C(e)\\) -- into \\(r\\) subsets, so as to minimize the total weight of the edges with end points in two different subsets (i.e. the edgecuts) and \\(r\\leq k\\) for a given integer \\(k\\).   \\(\\text{GPP2}(k)\\): partition the \\(\\dots\\) and \\(r\\geq k\\) for a given integer \\(k\\).   Both problems are NP-complete. The paper gives integer programming formulations for both problems, identifies the dimensions of the associated polytopes and explores conditions under which certain kinds of inequalities (non-negativity, cycle inequality, clique inequality, wheel inequality, bicycle wheel inequality resp. for \\(\\text{GPP2}(k)\\): spanning tree inequality, \\(q\\)-super-tree inequality, \\(q\\)-cycle-inequality, prism inequality) are facet defining.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$07C9B5C1-EC28-4F6F-8BC4-2D3AF4DD5D43","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":"Q2366610$22BA8D8B-48F0-40A9-8D1D-FBD0EAF6D91A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$4D22C78B-222A-4260-B6BD-6B5DC2BCBA11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$A2B7F76D-0995-443E-9DBA-507E4FD995BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$7A62A224-87D2-490E-B556-65ADFE1ED404","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd05c4084f13a0643ffc7567703559edf81f02c3","datavalue":{"value":"227183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$FF276A7A-5300-4833-9870-7A4288C3F28F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"263ce39a1c824aee01f047289ad732693743d085","datavalue":{"value":"facet defining cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$2CE660EE-27C1-46AD-A2F0-DE6B6CBC9050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$BC9A117E-3389-4DBA-88D3-CF49575A27CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd8c85d1991847addf4e0c6e4ea67af953543ba9","datavalue":{"value":"cycle inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$EFB033A6-B107-4482-A060-902AA68B7C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2248a70558833dbda07709aa2aebde6bb9563a30","datavalue":{"value":"clique inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$9B3D946B-3E61-415A-9F37-D8CC651EBC57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366610$1D41039A-8312-44ED-AE97-C8B5F043FD4E","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":"Q2366610$2CD074FB-B964-40DF-A326-FC3D95D8D132","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"273bb8be43b497baa3a710fb525da21d668a4d19","datavalue":{"value":{"entity-type":"item","numeric-id":3699730,"id":"Q3699730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$0ACA3DAD-3399-48D0-AD45-DFBB48F83A0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871b0b619dcdcfea503ebb95e9e10caab2448bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4726054,"id":"Q4726054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$E201CCC5-5BFB-4621-98AA-153A16E54A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"833ea50bd202261081ac55cf5d367cbccd0d3aa5","datavalue":{"value":{"entity-type":"item","numeric-id":1344221,"id":"Q1344221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$5184D890-17B8-4714-9B57-D8ACDCB40872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$BA22B675-351A-4498-8783-931CAAE87269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad561bb3ba40cd6dc94ec937533e92f2abed16f3","datavalue":{"value":{"entity-type":"item","numeric-id":5514166,"id":"Q5514166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$8BD0C000-E110-4C75-838C-16B1508026BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee8d7df28ef2adafb071115113b731f148103e6","datavalue":{"value":{"entity-type":"item","numeric-id":2639779,"id":"Q2639779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$683A4F22-2782-4B12-AF56-37FF5DE08615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6862ec6a29c3bb69f1c730fbdce7ad234e241ca2","datavalue":{"value":{"entity-type":"item","numeric-id":2639780,"id":"Q2639780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$335F393A-F862-4078-A4E5-84F9948F1A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f254aa4beacf34682044b841e9233d8cd989881a","datavalue":{"value":{"entity-type":"item","numeric-id":4027782,"id":"Q4027782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$F6993E4C-F9FE-4F7F-A04D-1D20D218992E","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":"Q2366610$80E87B85-03D0-42A3-9FCB-5B6D5DA6752C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6084bdc184628adc7fe57f950fb27bccae70ea2b","datavalue":{"value":{"entity-type":"item","numeric-id":752015,"id":"Q752015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$15CDADB5-C51B-4DD3-9682-E7E335A120ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8f80a19eef3ef00c63528b7a5312dd804775280","datavalue":{"value":{"entity-type":"item","numeric-id":1122492,"id":"Q1122492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$1F588A13-E931-4EC1-AF63-62F6CED982AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c36b42b281969cc247486ad758e619940ccb2d97","datavalue":{"value":{"entity-type":"item","numeric-id":4305362,"id":"Q4305362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$FEBAA142-6113-4681-9BC1-107C7FE4ED36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366610$93EA61B3-C0F6-4BA2-8FD0-4EBF0C089674","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ad6472860f37c84cb225270927cae144d1ea63f","datavalue":{"value":"https://doi.org/10.1007/bf01581239","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366610$18271AD4-B95D-4562-8ECF-9C662CBECEBD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6d9bee5da312734fe26799fab4558e729568eb9a","datavalue":{"value":"W1993052292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366610$C05DFD1F-C0DC-4859-861C-AC95BEEA854B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8478bcb70497a9cc3d5ff09b6d78e49150d1e4a","datavalue":{"value":{"entity-type":"item","numeric-id":2467133,"id":"Q2467133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bdf175fcb0c4e1a60ac319b0ff1328fab94d0b7","datavalue":{"value":{"amount":"+0.8416890501976013","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":"Q2366610$6A015F31-FB16-4450-B526-E829772296FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"665c262392b2e2251f68422928b2598c48ba5bab","datavalue":{"value":{"entity-type":"item","numeric-id":1751250,"id":"Q1751250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a20369bd269730fc8ae27419ea4555dc346917b","datavalue":{"value":{"amount":"+0.8379778861999512","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":"Q2366610$D3446967-688F-4F0C-98EC-9DD644B6DB33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f63bcdf560f72fb74b4a16df2d380556e76a083e","datavalue":{"value":{"entity-type":"item","numeric-id":752015,"id":"Q752015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b67b01e3e5505b6232ac2e93a20801d35e46656","datavalue":{"value":{"amount":"+0.8239941596984863","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":"Q2366610$BA276C9A-A08C-469B-9EA9-91D5E74B8723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0b22fff08f67533f825318f776243ef21e5df1a","datavalue":{"value":{"entity-type":"item","numeric-id":1290618,"id":"Q1290618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9768efa5b185d047255807dcfdd0d3d2e4748e54","datavalue":{"value":{"amount":"+0.8201112151145935","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":"Q2366610$09277560-10B8-4A60-8EC4-FB7C69B3D53D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7327a3436de5df3718288da14317e41c64a0b23f","datavalue":{"value":{"entity-type":"item","numeric-id":1814793,"id":"Q1814793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcb08ca2e86acb974fd5723a6b8f5a28b46da477","datavalue":{"value":{"amount":"+0.816152036190033","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":"Q2366610$D1CAED64-0385-4BED-A971-3D410DE41033","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366610","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366610"}}}}}