{"entities":{"Q1079494":{"pageid":1090246,"ns":120,"title":"Item:Q1079494","lastrevid":48961921,"modified":"2026-01-06T08:09:13Z","type":"item","id":"Q1079494","labels":{"en":{"language":"en","value":"A solvable case of quadratic 0-1 programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3963565"}},"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":"Q1079494$CAEDE119-32FF-4D98-A259-D5AB1CD29DB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3daeac67325b694b75ba124eb05ae4ed4670509","datavalue":{"value":{"text":"A solvable case of quadratic 0-1 programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079494$7BCBDD7F-3F5A-4040-ACED-99E00357CDD7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81fd8da6f53fb8f33659549ebdc8e6dc8e8c3190","datavalue":{"value":"0597.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$BE1E4A4C-6A09-4A05-BC93-380BDF7EA52B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb162df3b7d0a5f4cc4c38e76b26069f402e4128","datavalue":{"value":"10.1016/0166-218X(86)90065-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$CFB53C1D-B3D5-4ACD-8355-59AE99070A31","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$7F1A1468-AA64-4DA4-A37A-FB2EB06DE3F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1079494$DCB25F16-FDE8-449C-A851-93BC99244ED6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4518c82c7e6741d6b19c7b3d518ba8c6aff3a25","datavalue":{"value":"The problem of minimizing a quadratic function \\(f(x)=x^ tQx+cx\\) with symmetric matrix Q and Boolean x is considered. Finding the minimum of f(x) is equivalent to finding an assignment of values to the variables \\(s_ i\\) \\((s_ i=2x_ i-1\\), \\(s_ i\\in \\{-1,1\\})\\) that maximizes \\(\\sum \\{w_{ij}:\\) \\(s_ i=-s_ i\\}\\) where \\(w_{ij}=(1/4)q_{ij}\\) for \\(1\\leq i\\leq j\\leq n\\) and \\(w_{0j}=c_ j+\\sum^{n}_{i=j}q_{ji}\\) for \\(0\\leq j\\leq n\\). This is equivalent to finding a maximum weighted cut in the graph \\(H=(U,F)\\), where \\(U=\\{0,1,...,n\\}\\), and \\(ij\\in F\\Leftrightarrow w_{ij}\\neq 0\\). The case when the graph \\(H=(U,F)\\) has a vertex u such that \\(H\\setminus u\\) is series-parallel is considered. In this case an algorithm having computing time 0(n) is proposed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079494$5D7A80B0-7E73-45B9-BB57-2FE0E9706A3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$40D3352B-E971-4716-B4F8-7C171F609EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$219363F0-39DE-46F7-8450-38098C55EACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$EC4DFBA4-5E5C-4578-BC67-1AD47A04BB23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$CE6C5442-E416-4843-AC6A-C875ECE6179F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f84e632253d3a73c5a80988035f0340414c4d494","datavalue":{"value":"3963565","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$8AF8190A-8E3B-432E-A905-0F2C600A122A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d665173dc81790294af37e94b0e9f3bf8df667fc","datavalue":{"value":"max-cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079494$FBD24967-8A9E-41FA-9694-49F340F8667F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a510d0e1f5e32a9431a9f0eab9e73a0d22719a0","datavalue":{"value":"maximum weighted cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079494$7AB5CA2B-015B-4BA8-951E-99878D4974FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db155a1931c450924f78e9052809373e70af6db8","datavalue":{"value":"series-parallel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079494$8CED0F38-27F0-4E88-9AF3-48F9C6AE6970","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65634c2d7f7dfc4f36bec0cd396792e04d171618","datavalue":{"value":{"entity-type":"item","numeric-id":270026,"id":"Q270026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$187B2F82-E82E-468F-8FBE-90EE4F6951BD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3ba912c6c747366fcbf58ca77660b129d8633c6","datavalue":{"value":{"entity-type":"item","numeric-id":1014034,"id":"Q1014034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$C0015CF1-AD54-4A28-B854-BCF5E70C46E5","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":"Q1079494$EA018F8B-D10C-474D-9C8A-825FC4B15783","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"175916359d5356dd13dd1efc4a7517f1e19ef4c3","datavalue":{"value":{"entity-type":"item","numeric-id":593988,"id":"Q593988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$7FB8EBB8-1695-49DC-AFD9-8525C211792E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b4b0263bf157bc56ee9f4278362c292a571a65","datavalue":{"value":{"entity-type":"item","numeric-id":1147168,"id":"Q1147168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$8CAF57F8-E666-4E08-8DC9-F5B5FD866F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ae5ab26cbeea37c1d0862dd4a538380dfffc97","datavalue":{"value":{"entity-type":"item","numeric-id":585083,"id":"Q585083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$F9F71A93-5FA1-40A0-BE70-7A2203D75CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$FDA70EA7-DB56-45AD-8EE3-5A65337FA6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$A794B2D4-D5F3-45EF-BCD1-19A7C35A9DA5","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":"Q1079494$BBCB0E2F-B21E-47A7-9D0E-4EC6F6A06C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c71b74d85909c198a1d042cf4a28cc81c40fe0","datavalue":{"value":{"entity-type":"item","numeric-id":5341344,"id":"Q5341344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$C42332F6-783C-42BB-8F83-4372F17F1992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1e239dce14973bc963cb9871e26501ddc153e9","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$4EC4AD4F-9ABB-47A2-B2FC-7B8B47E9C0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07827ff8219cf85dba399be8ca430be733102ca6","datavalue":{"value":{"entity-type":"item","numeric-id":3863696,"id":"Q3863696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$0221331E-86B7-4BBA-B369-CDE03605115E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb1971476988dd1583d8582c2332379ed61a85fd","datavalue":{"value":{"entity-type":"item","numeric-id":4090127,"id":"Q4090127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079494$EE8877DA-83AC-4E6D-9A81-F3DBA742FAAB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c3d6d2204bbe09d2a264fbd3ef28647e024ef52d","datavalue":{"value":"https://doi.org/10.1016/0166-218x(86)90065-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079494$C2F37C70-EFB4-4674-9350-5789FD160469","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ce9b38113ab51c9f37a93016e0f4751e736b857","datavalue":{"value":"W1973069886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079494$B8271EB0-BB35-45CA-A364-8B661D028D62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eac954f6df60e09ed199ce27b1e7259f3725ff0f","datavalue":{"value":{"entity-type":"item","numeric-id":1193723,"id":"Q1193723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f798e8a1a290148793e10552048e540194a8ee70","datavalue":{"value":{"amount":"+0.8701781630516052","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":"Q1079494$4D0D2D3A-4E90-41DD-B6C7-271ECE04E6C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"124ca194bbeb90aa266cdbe87a9091e3cc35773f","datavalue":{"value":{"entity-type":"item","numeric-id":5955560,"id":"Q5955560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5bde32b03ca26a00b37f6e96137ad742b32d19c","datavalue":{"value":{"amount":"+0.8672455549240112","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":"Q1079494$63FF727F-6C81-4673-B48E-EC10E3892D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30ab3d825df9298a9fe4474ccd65cd76e3114004","datavalue":{"value":{"entity-type":"item","numeric-id":1123806,"id":"Q1123806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5bddf68542857c675cd2214950356d28cfebbc2","datavalue":{"value":{"amount":"+0.8317083120346069","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":"Q1079494$89005533-7E01-46B9-A9A2-70A9FBC3B391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a625058fce336395cad1f2a1e7902378d57a9790","datavalue":{"value":{"entity-type":"item","numeric-id":3802912,"id":"Q3802912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00d68a112aa3e3b5763f58369ef859fa3457c951","datavalue":{"value":{"amount":"+0.8259006142616272","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":"Q1079494$058AF964-E24F-473D-A647-1A37FCBC94F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d79cac08eb6ee61668f44e2fb81b88c9725ccda","datavalue":{"value":{"entity-type":"item","numeric-id":801811,"id":"Q801811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e662d679830e359dd7e6696e64ddc1d4211d549e","datavalue":{"value":{"amount":"+0.8199185729026794","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":"Q1079494$19E69FFA-783C-4153-92E4-3B0A88E4EA7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1079494","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1079494"}}}}}