{"entities":{"Q2436653":{"pageid":2447396,"ns":120,"title":"Item:Q2436653","lastrevid":57922503,"modified":"2026-04-03T02:37:25Z","type":"item","id":"Q2436653","labels":{"en":{"language":"en","value":"Convex optimization for the planted \\(k\\)-disjoint-clique problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6261684"}},"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":"Q2436653$0396F44E-AAF3-4F0A-9EC8-1C344ED50FD6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d0729e523d09ef105c5eba168c5f7d2c79fb2f9","datavalue":{"value":{"text":"Convex optimization for the planted \\(k\\)-disjoint-clique problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2436653$005789FC-4AF8-4A1B-B2A8-CEFB2CFB7755","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"899e1db31829437bc406c8eb6902f6cbf5b6d0b0","datavalue":{"value":"1291.90194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$8EF328D7-D457-45B6-84A4-9EEE2A46FCF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"19314e3717055044c35e04dfd4d786bc91a8affd","datavalue":{"value":{"entity-type":"item","numeric-id":687093,"id":"Q687093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$C86A71F3-3E5C-4195-AFE8-747E3B4E2771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd6ec83983f84f1d1b23b231eff6fb1b7898049f","datavalue":{"value":{"entity-type":"item","numeric-id":301681,"id":"Q301681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$8F589DBC-D68A-4807-8634-8CA19E17151E","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":"Q2436653$7DF09BB7-FA52-4548-BD4F-F0161BC8EECD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"efe2faed09c4ec490640e4d710dd813f29d8297b","datavalue":{"value":{"time":"+2014-02-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2436653$E7008332-5936-4E8F-8096-DF960D8F3720","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b1c8f54b43a0f3202b87a0a20e6df32cb16ebd7","datavalue":{"value":"https://arxiv.org/abs/1008.2814","type":"string"},"datatype":"url"},"type":"statement","id":"Q2436653$524CAF44-EC50-4429-BD33-7EE83AE251F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6bcf1bc7dda2256dc1e117985e3568b26ef84c7","datavalue":{"value":"The authors consider the clustering problem for graphs. More precisely, given an undirected graph, the problem is to find a certain number of disjoint cliques that cover the maximum number of nodes of the graph. This problem has numerous potential applications, since clustering aims at partitioning data into sets of similar objects.  Whereas the exact clustering problem considered by the authors is NP-hard, it is approached with a convex relaxation that can solve it in polynomial time in some specific cases which, as argued by the authors, are practically relevant. These cases include graphs consisting of a certain number of disjoint large cliques perturbed by some diversionary nodes and edges added either randomly (noise) or by an adversary.  The classical convex relaxation approach followed by the authors consists of formulating the underlying combinatorial optimization problem as a (linear hence convex) semidefinite programming problem with a (nonconvex) rank constraint, and then relaxing the problem by dropping the rank constraint. Under the assumption that there is a solution of given rank (which corresponds to the existence of an unperturbed graph consisting of disjoint large cliques, and a bound on the number of noise edges, see the main result Theorem 3.1), the authors can prove a posteriori that the convex relaxation exactly recovers the combinational solution by constructing dual multipliers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2436653$D7C9CC7F-3C96-4AD9-A188-AED39D05759A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e54b147dd6c7bd2f594ffe4bf0977496876b0eaa","datavalue":{"value":{"entity-type":"item","numeric-id":248042,"id":"Q248042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$F0CABFE5-6483-446D-B021-ADC3E74203AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$5C92EB61-B81B-4A42-9206-8BB161846C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$AA1CBF5E-891A-4D2E-B74F-FB3A2E024F75","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"21df591efc772b7dc0adf36684865a52481b1111","datavalue":{"value":"6261684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$F05352A2-F3B6-4B20-8A57-4B7C5626454C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2436653$6E55AB97-3261-4DAD-A5D5-138DA2FBEE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0145dbb175f229104a70deaeffc1099143a20d","datavalue":{"value":"semidefinite programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2436653$E3CB0276-194D-4753-BFC8-0F58F7091EF1","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":"Q2436653$D3E2EEF8-7EF8-41AF-BF43-6B8B5DD5A3C7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f855f42ccffdb84ea076c5a893fcfd288da6808f","datavalue":{"value":"W1936234780","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$8D51F2EE-F06F-4F76-A7AE-6681389B4430","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2f336cb3f440ddbefc95e06e53e92b90c8bb996","datavalue":{"value":{"entity-type":"item","numeric-id":4705344,"id":"Q4705344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$B95C9129-8596-4773-99CE-4BAB40FDB2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e46797b520f23f20e9db17b00abeae02757a2bca","datavalue":{"value":{"entity-type":"item","numeric-id":717132,"id":"Q717132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$918D5E4F-D2EF-42D7-B851-C5B1DC737FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0235cb621e497cf4d26091fba0f8ba3bbba91a30","datavalue":{"value":{"entity-type":"item","numeric-id":3016258,"id":"Q3016258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$5D639E2E-B659-478E-AEA5-8853D987C392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8f51123d4849920c0bd477136f67ae685bea6fb","datavalue":{"value":{"entity-type":"item","numeric-id":4821526,"id":"Q4821526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$84F43AB3-E483-4EF6-A54F-FCBB33A77128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cdd9ea1058aa803df34da47c73be3afe11b3e31","datavalue":{"value":{"entity-type":"item","numeric-id":2655288,"id":"Q2655288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$9594CE85-F09B-4EBD-828E-05FC2584850C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb9a79459a4bab5fa533a4553359293bd77a037d","datavalue":{"value":{"entity-type":"item","numeric-id":3093595,"id":"Q3093595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$98713B7D-D049-43E0-B90A-9C167F518FB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ec1447f55154124b9721201dc247b2694f2ab5","datavalue":{"value":{"entity-type":"item","numeric-id":4948021,"id":"Q4948021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$9F3E56A4-F8B4-494B-BD9F-FC89D958FA0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3009684eb7945556c56793ee792b9b228bab1d6","datavalue":{"value":{"entity-type":"item","numeric-id":1169017,"id":"Q1169017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$292451EC-5FDC-4167-A085-DD3D87179288","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":"Q2436653$47A63218-07EC-470F-8F40-91D49151AC96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ee1ad14aa053beecba249038b4ef187c6a9b419","datavalue":{"value":{"entity-type":"item","numeric-id":1137308,"id":"Q1137308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$FD7223C6-AC40-47DC-9DDE-42E6DEA3C968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d52df2154bfdd0f3ced81e7603ae5503222445b","datavalue":{"value":{"entity-type":"item","numeric-id":5689624,"id":"Q5689624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$A4659BEF-6A3B-4E33-8F79-D24CD34DF4B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$E4A849D1-7ACA-4DA8-8AA6-1E2EEBE877DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96b1a3962fbf13b0ab48bc4931d20589e15128ef","datavalue":{"value":{"entity-type":"item","numeric-id":2934076,"id":"Q2934076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$70549F9A-A1D4-40FC-99AC-4C83022C8D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ba3bd74ef41e0757015be3b53bca7ad9cb71ba","datavalue":{"value":{"entity-type":"item","numeric-id":5463630,"id":"Q5463630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$BAFA48BA-EA6D-481A-AC52-C7E27D5ADEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5543e119650811c9648ae3bc0f721e47a5bddc1f","datavalue":{"value":{"entity-type":"item","numeric-id":5395696,"id":"Q5395696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$A11051CE-5661-4FF2-8278-04364212C928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec9d0ddb37d523af0c0834265d31bef8c20ef92b","datavalue":{"value":{"entity-type":"item","numeric-id":3586174,"id":"Q3586174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$7F766CE6-2C00-4DBD-B2F9-48163200DAE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0521b18be13f5900fdbc4f3d03d2eb9ac58e8664","datavalue":{"value":{"entity-type":"item","numeric-id":3058503,"id":"Q3058503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2436653$DAAB6795-25C8-4046-BD58-7D4AAAA31A41","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4349f3e7b740254a642a8d302a252d02bc825583","datavalue":{"value":"10.1007/S10107-013-0733-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2436653$80E7C48E-4740-4D7C-9AE2-04010BCD610F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"386d773303e973cace17292f4c07e4df111e252d","datavalue":{"value":{"entity-type":"item","numeric-id":896191,"id":"Q896191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3fe93515ee90668801f1372f364c5f34ec6d42a","datavalue":{"value":{"amount":"+0.7860941290855408","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":"Q2436653$17C1FDF5-117C-4948-9C3F-C557241C16B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50085760d90f7035351a0315b63c8a34c380ccff","datavalue":{"value":{"entity-type":"item","numeric-id":142862,"id":"Q142862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28cd4d61eea82bd69da3b4568d7697565cbb310a","datavalue":{"value":{"amount":"+0.7690494060516357","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":"Q2436653$11FB0CDB-9CD3-43CD-A103-A8434E02615D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da0898158842660d44ba97490d34b4ec4a44fa01","datavalue":{"value":{"entity-type":"item","numeric-id":463740,"id":"Q463740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e32d1263bf3e47c43fbde1db5d4979464c49c20","datavalue":{"value":{"amount":"+0.7652990221977234","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":"Q2436653$E9D9EDA5-68BE-45C7-B25D-5326CDAC0072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9af5500fc42fcdd2cc9d77d2fb242beee4ae9378","datavalue":{"value":{"entity-type":"item","numeric-id":2934076,"id":"Q2934076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7f0466b54366a30c415ce952416e912ed8fd4e3","datavalue":{"value":{"amount":"+0.7440946102142334","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":"Q2436653$584C8EFC-B925-441B-9312-F89747FF844B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7bddaad493610207f0c2b3a042eed39d801f326","datavalue":{"value":{"entity-type":"item","numeric-id":4633040,"id":"Q4633040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8821f3f1b1445a2657abd61dbe4b48b0aa8f0b50","datavalue":{"value":{"amount":"+0.7437453269958496","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":"Q2436653$F8F39DAE-D930-4412-859C-CAE747546014","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2436653","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2436653"}}}}}