{"entities":{"Q439900":{"pageid":441667,"ns":120,"title":"Item:Q439900","lastrevid":61935684,"modified":"2026-04-11T02:40:01Z","type":"item","id":"Q439900","labels":{"en":{"language":"en","value":"Complexity results for the gap inequalities for the max-cut problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6067684"}},"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":"Q439900$AE85C261-A36C-450B-8E95-BF6D08DA4BE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"328c2a20e4e054ede9d5d724b15076b4afafe251","datavalue":{"value":{"text":"Complexity results for the gap inequalities for the max-cut problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q439900$80DDE427-22F9-4B4B-8FF8-08AF351479DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9cfbf6a045528a369681bc6601a8fa225dd1a19b","datavalue":{"value":"1245.90101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$388F1238-408E-4D76-A778-DF82CEC48052","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c635c0cf6e0401e0413f2d6f0a79d82f0ed5098","datavalue":{"value":{"entity-type":"item","numeric-id":408379,"id":"Q408379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$56F914FF-6962-414A-97CA-17B0F1E8CABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0525d4f441c8d39ff7a0a760039a608fc7dda78e","datavalue":{"value":{"entity-type":"item","numeric-id":408380,"id":"Q408380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$D06FA5BC-FABD-4C7D-86CF-2A8943410848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7cc27fc1dd4236c294e0ec74bd11801150d0f456","datavalue":{"value":{"entity-type":"item","numeric-id":185370,"id":"Q185370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$6B40ED0A-0601-42BA-ADB4-3FF125D921A1","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":"Q439900$853B9CEF-FDFA-4CDB-AEB4-75EC58EE585B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b603f6512fef6ae8133f8f1ff885bde2efd37af6","datavalue":{"value":{"time":"+2012-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q439900$54F5924A-BF58-4BB2-A20B-B17A7B298C42","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$A2CE6D64-1653-459B-88DB-73C1CDDDD882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$2DEC97A2-4797-471D-A2A8-FD726A1D0F38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$B65412FC-5AF7-4548-B5DA-1FD9F44EE9C9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43fdd84c0fbde70bf1d9e600e0a32c5fc01e60b6","datavalue":{"value":"6067684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$5493C310-1D2A-4C27-9A63-3399C75B76F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q439900$1B276376-1923-47B6-80FC-519B264A6FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d665173dc81790294af37e94b0e9f3bf8df667fc","datavalue":{"value":"max-cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q439900$ED7D1B34-0CD3-420F-BC6F-B54376BF49EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be3f5c88d3db777a4bdd3348a5d62b7e04a937f6","datavalue":{"value":"cutting planes","type":"string"},"datatype":"string"},"type":"statement","id":"Q439900$691E7158-40BA-493F-807C-EC7AF3A4F41D","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":"Q439900$A5C4915D-33F0-487D-952A-C26F918D250E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"de77971e62d150e7361d47f2210a3585e44634c5","datavalue":{"value":"Q57702158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$FA48F1C9-1B35-4E34-B389-364F27D80C5C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3f66556586d57c0a2402cbcba6d830a2e55e7f72","datavalue":{"value":"https://doi.org/10.1016/j.orl.2012.01.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q439900$E1916F50-D9F3-4AAA-9E14-838EAAB39B5D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fec5bb29f3bb81dc0a048adc36ef53da269871c3","datavalue":{"value":"W2169764437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$E2AFCBEB-16DB-4C5A-9C6B-37CCC5CAF9BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d259358356971ee1979ce5b0de7364af144bc3dc","datavalue":{"value":{"entity-type":"item","numeric-id":5897088,"id":"Q5897088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$85B1003E-592E-4721-ADCA-2B81DA0AFA75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0afb9fd1c85f2ab3df2128e318388af8da1f75","datavalue":{"value":{"entity-type":"item","numeric-id":1803268,"id":"Q1803268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$2F0E07B2-5C01-4B21-AEDF-DF214C70A86B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51d40f6a981842bd7d68af7d36318ad81cedc0f","datavalue":{"value":{"entity-type":"item","numeric-id":1403298,"id":"Q1403298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$DD8F8FB7-44E1-4532-B8AE-B6AAF6697567","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":"Q439900$37DDDFA3-139A-451B-AAB0-E8C101498954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a860092cae4ad4c5ee631c0a98f0a7ee7f9c9d0","datavalue":{"value":{"entity-type":"item","numeric-id":3241581,"id":"Q3241581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$F55A59FE-D794-40AE-B53E-17FB07E1E7D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ed0c930316f48e738cf8137ac6a1ec96a6008a2","datavalue":{"value":{"entity-type":"item","numeric-id":3565241,"id":"Q3565241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$A8BEDE10-8CE4-4E4D-ADEA-9C466D366237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc83c5f291c0806fae8dc4dfc1516d389930f923","datavalue":{"value":{"entity-type":"item","numeric-id":1316645,"id":"Q1316645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$B8C3DB41-6158-4694-BA36-FA0394F39993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"235eefc42a64a79673bb70d93ca06d1427649078","datavalue":{"value":{"entity-type":"item","numeric-id":5906765,"id":"Q5906765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$69C17E62-E1CE-4E06-B07C-53F3DECF6C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc47f0c6297f246fdc8fb3b01226819c409e5fca","datavalue":{"value":{"entity-type":"item","numeric-id":408381,"id":"Q408381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$77BB466E-7384-442C-AA6F-DC451DEB7C2B","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":"Q439900$86614B31-CA46-47EC-9286-3D8EA47ED4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$146B29CF-D35E-44BA-B00B-CE3450578495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97e4bb76b1e06f3821b076b09601d70ca00a8869","datavalue":{"value":{"entity-type":"item","numeric-id":2490329,"id":"Q2490329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$42A450ED-35FB-449E-BF5F-E7E3EC2ECEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$601BA7A6-67EA-43AB-9F66-C89D26724FE9","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":"Q439900$AB1D967F-ACE2-41AD-9244-C26F0232BDC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1dfdd337b99f05233da283167f6f73cb1de747","datavalue":{"value":{"entity-type":"item","numeric-id":4089444,"id":"Q4089444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$39AD9EE9-CE53-4D19-A665-616319D96D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"204e3d442e001b10cf81a42ec10fdec67b35d567","datavalue":{"value":{"entity-type":"item","numeric-id":4398372,"id":"Q4398372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$28033E61-4DAC-4B0D-97F7-525617D6CE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0711f1d1d42419550964f4c8ab24c2e9cf7bc154","datavalue":{"value":{"entity-type":"item","numeric-id":4891696,"id":"Q4891696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$9EFAD6EB-2CD9-49CA-8EC3-4B128D33EC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51218dcf79fccef6aa191f5e37e405fd5d23ebda","datavalue":{"value":{"entity-type":"item","numeric-id":1894508,"id":"Q1894508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$F4639B18-5AC9-459F-8C15-5A0D9AE95E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3ae86e948923805837651b9b9d288cf4fdba96e","datavalue":{"value":{"entity-type":"item","numeric-id":662294,"id":"Q662294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$AE749CB1-0E9C-496E-B7ED-BEACB3CAACFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4903f204d229fe512dea32aafa7edcd24d83ed69","datavalue":{"value":{"entity-type":"item","numeric-id":5771312,"id":"Q5771312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$A765F5D8-23EC-4401-859D-AFED2FFB7D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3223323d1c6215bfb2ca00fac2471a05c75ea3b1","datavalue":{"value":{"entity-type":"item","numeric-id":3287702,"id":"Q3287702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q439900$6A714C9E-0888-4722-9019-809D725E241F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d17a6bdcee0f6cfa270bb9ca8108c020450c401","datavalue":{"value":"10.1016/J.ORL.2012.01.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q439900$2535C2A6-5CC2-4A54-A261-E120320E7BDA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510f5978423a10b60d1d793c0662fb24adb97261","datavalue":{"value":{"entity-type":"item","numeric-id":3167623,"id":"Q3167623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee84a606f3f326dafc69b9665c21c6f745d64df3","datavalue":{"value":{"amount":"+0.8846354484558105","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":"Q439900$46211405-0121-49EA-AC8E-6D19CD8ECE2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"617896d8b8e935d51571003249e751d49880a985","datavalue":{"value":{"entity-type":"item","numeric-id":1911843,"id":"Q1911843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4a06d246e82c60bff06b7fbf92b2663b5b33a2a","datavalue":{"value":{"amount":"+0.8180417418479919","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":"Q439900$28952707-A57F-4D1F-9F32-98D4D1946510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"773322ac604225df3aeae2e869712759bd0c02bc","datavalue":{"value":{"entity-type":"item","numeric-id":1411614,"id":"Q1411614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ecf7a3b59af2ff4dbfb76e83499b1496254b3e9","datavalue":{"value":{"amount":"+0.8177698254585266","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":"Q439900$436E5F28-78E6-44FE-9A9F-BAADAFF6647B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b51d82ee8968c2aeacdc317b8f734c71b553be41","datavalue":{"value":{"entity-type":"item","numeric-id":2417185,"id":"Q2417185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a12a2e50882225a590dd41bbb105df1c6dc712f4","datavalue":{"value":{"amount":"+0.8003690838813782","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":"Q439900$203BA39C-4C8F-45C6-83A2-C03D8BE8445F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c103da5e0c426284b53c9ca01d1af839e5a4ce5","datavalue":{"value":{"entity-type":"item","numeric-id":408381,"id":"Q408381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6879ec2a91f92095016a34699b1fb7c0109cda05","datavalue":{"value":{"amount":"+0.7920428514480591","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":"Q439900$6DDAD91F-4F3C-478D-84FB-A939BAC09114","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity results for the gap inequalities for the max-cut problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_results_for_the_gap_inequalities_for_the_max-cut_problem"}}}}}