{"entities":{"Q685307":{"pageid":687156,"ns":120,"title":"Item:Q685307","lastrevid":63457431,"modified":"2026-04-11T13:17:22Z","type":"item","id":"Q685307","labels":{"en":{"language":"en","value":"Combinatorial properties and the complexity of a max-cut approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417229"}},"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":"Q685307$B5B1743B-96C8-4382-9446-7917A329F57F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c914ff1e61290cf7142e316b05d060d83508022f","datavalue":{"value":{"text":"Combinatorial properties and the complexity of a max-cut approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685307$7944AFFD-81C2-4B79-BCD0-A64ADAD6B19A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78851bf6b68f754456dc77106d9bd980a0de3ee6","datavalue":{"value":"0780.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$4D327DB5-E489-419D-901A-63AA4156ECBE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"989a9701d150170acf3a0218ce39685294f0c3e7","datavalue":{"value":{"entity-type":"item","numeric-id":195165,"id":"Q195165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685307$C0EB553E-28FE-4273-8798-6CC4402EACE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"697be813fbdf5940bf37c14fbe59ac96ce0fdc57","datavalue":{"value":{"entity-type":"item","numeric-id":685306,"id":"Q685306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685307$29D27073-B107-452D-97CC-26F0213215B4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685307$91DABEFA-63E5-4B72-87E2-E4D181726411","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7749606556d7f0cc2f0d99e82d171059b0e62df","datavalue":{"value":{"time":"+1993-12-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685307$1376CF9B-86EF-4DA6-89AE-F614570D296D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae3c20ad9976b69ae362fd136128e6e3a39a65c5","datavalue":{"value":"In several combinatorial optimization problems one can effectively use eigenvalues and eigenvectors as a kind of easy solvable quadratic relaxations. This approach proved to be useful in many instances (see a recent survey by the second author and the reviewer [Eigenvalues in combinatorial optimization, in ``Combinatorial and graph-theoretic problems in linear algebra'' (1993)]). Max-cut is one of such problems. The authors investigate combinatorial properties of an eigenvalue upper bound \\(\\varphi(G)\\) on the max-cut of graphs. It is shown that this bound behaves in a manner similar to the max-cut for several operations (switching, contraction, vertex splitting, decomposition). It is conjectured that \\(\\varphi(G)\\) approximates the max-cut of \\(G\\) within the factor 1.131. This conjecture is supported by some results showing that the eigenvalue bound provides conjectured approximation for the max-cut in many interesting classes of graphs. The importance of these results lies in the fact that no efficient approximation algorithm for the max-cut problem has been found so far.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$B5A51472-E67E-4327-ADF3-35F64E430F63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"abf255b967b94e917e05e1834cde56652b9b0e09","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685307$EF324AC0-C86C-4E0C-8ADC-820E3BA70952","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$369AF655-E7CC-4608-8C98-38B22378ECCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$3E0DAC06-F5A6-4100-9AC0-1423255243AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$B33DA887-AB35-40B3-938B-B06FB915647D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$D847213F-73E1-48F7-8E03-CBCB412F2426","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"23d734741da590edc50952f03941bef72e8dfe43","datavalue":{"value":"417229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$5504A867-3C92-4C38-9AE7-B39E1A20B8A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$4204F3DE-F3B7-4102-988E-39037BC96D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$BDADD856-A7AB-42AA-9744-1227A319507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$EEC2B8C7-6E56-4150-B382-0EC56B671946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"811604a75801fcd709c8667f83ea26944825b8d2","datavalue":{"value":"eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$73774C17-EA37-4ED3-8C15-B10445FB46E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52eea320300e07df842062e5b7cf401deee61277","datavalue":{"value":"eigenvectors","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$687A10E1-6856-4A2F-A198-FA2E00C616A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a82fb19c1a78ebdb80ce09fcea99589743cc6fd","datavalue":{"value":"max-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$A2805A7F-C020-4633-84CA-31D64ED10E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q685307$A557744B-4DF8-46F3-8497-0052E0539BF4","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":"Q685307$68D37112-AB1D-494F-AA0E-E072C9599FC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6b3708f7021df10d5b4deb459e87f000a5c2da1f","datavalue":{"value":"https://doi.org/10.1006/eujc.1993.1035","type":"string"},"datatype":"url"},"type":"statement","id":"Q685307$285D6B10-2210-4DD1-AF76-A55A1A710931","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7abc467a4cbaebf18f5800c60477b8fea5b8a567","datavalue":{"value":"W2014079391","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$0B36130E-DB7A-49ED-B7AF-930417EBD9E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"589521a0e11609e89af6d8d845bf8830c8ac39d5","datavalue":{"value":"10.1006/EUJC.1993.1035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685307$845F0FB1-3A23-4987-8566-445282104D9A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d3678c5d11ea1a5c12328fbd71a731a040ad6a5","datavalue":{"value":{"entity-type":"item","numeric-id":686456,"id":"Q686456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eb789d7d202a18b4d471ea5237e45572c87c35b","datavalue":{"value":{"amount":"+0.9110392332077026","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":"Q685307$CEF8BA45-769F-471F-AD62-0655C7C96C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9626daed0bb58dbafdc10ff7960cd6098acb8352","datavalue":{"value":{"entity-type":"item","numeric-id":1319025,"id":"Q1319025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eb789d7d202a18b4d471ea5237e45572c87c35b","datavalue":{"value":{"amount":"+0.9110392332077026","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":"Q685307$D100FD04-2FA7-4E74-8B60-8A0127EB8EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f9e534336d748d0ca163505f11a36890b74109b","datavalue":{"value":{"entity-type":"item","numeric-id":3137209,"id":"Q3137209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fbdd9a57912956d325bae747b8858101fdfa494","datavalue":{"value":{"amount":"+0.8582523465156555","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":"Q685307$02E291CA-DF2F-48CA-A89E-4A13A09AD126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6b3046e2c652be128d1f1c69eab689a4357ec13","datavalue":{"value":{"entity-type":"item","numeric-id":4840774,"id":"Q4840774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fbdd9a57912956d325bae747b8858101fdfa494","datavalue":{"value":{"amount":"+0.8582523465156555","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":"Q685307$3395C1D8-1D33-464C-A87E-3249CEEE9F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ef3b83849a2357f415122f5245a8febeabb574d","datavalue":{"value":{"entity-type":"item","numeric-id":1900149,"id":"Q1900149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56afdffc12edc245ad300efcb3a57994e6356bd4","datavalue":{"value":{"amount":"+0.8430249691009521","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":"Q685307$6C7C32BF-93D4-4669-AC2B-D0FFD897590F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Combinatorial properties and the complexity of a max-cut approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Combinatorial_properties_and_the_complexity_of_a_max-cut_approximation"}}}}}