{"entities":{"Q380664":{"pageid":382431,"ns":120,"title":"Item:Q380664","lastrevid":61404537,"modified":"2026-04-10T23:09:24Z","type":"item","id":"Q380664","labels":{"en":{"language":"en","value":"Reoptimization of constraint satisfaction problems with approximation resistant predicates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6226969"}},"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":"Q380664$4C56B646-1933-453D-AD06-2EA5FE8730DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7bef32c8bbb85dd61c803862bb1aff7dd33d7cfc","datavalue":{"value":{"text":"Reoptimization of constraint satisfaction problems with approximation resistant predicates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q380664$ECB1CE14-EA21-4FCC-AC91-2341B8CBDF39","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"46d55f0ab203f27aa321bfcbfb07d20051e78884","datavalue":{"value":"1290.90074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q380664$72437682-F603-47C0-8237-3450321E7945","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ac60fa2d2adc80c0cfe9b12a6aba5eba7e810aa","datavalue":{"value":{"entity-type":"item","numeric-id":334237,"id":"Q334237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$6EEB9038-003C-44E7-A19B-AD408553EC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f280ea3ec12f1ef6ec2257a3ac7f202db738feee","datavalue":{"value":{"entity-type":"item","numeric-id":424644,"id":"Q424644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$DB4F7703-4459-4A05-8E62-52AE36D89579","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1b023419c56b9969f2d98b08637e9b0af86a936b","datavalue":{"value":{"entity-type":"item","numeric-id":199816,"id":"Q199816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$2C7E85DE-080E-47B8-BB90-C5AA793113F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"108246dca772a8e1d58c3ba11f0cdc16c904d0dc","datavalue":{"value":{"time":"+2013-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q380664$91F25D4D-8BDB-4D70-88DF-868C501E2C3B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"765861810bf0d63e173e7342a06da4507302799d","datavalue":{"value":"From the Introduction: ``Constraint satisfaction problems (CSPs) are generalizations of many discrete optimization problems. In such problems, constraints are specified by a \\(k\\)-place predicate \\(P\\). In particular, the Max-CSP-\\(P\\) problem is as follows: find an assignment of truth values to variables that satisfies the maximal number of constraints. Here, efficient approximation algorithms for solving such problems are considered. [\\dots]  As is well-known, the problem Max-CSP-\\(P\\) is \\(NP\\)-hard for predicates \\(P\\) that depend on at least two variables. Of interest is the determination of an efficient approximation algorithm for this problem. A trivial algorithm consists of assigning random variables to variables. J. Hastad has shown that, using these random assignments, an optimal approximation algorithm can be obtained for Max-CSP-\\(P\\) (with achieving the approximation ratio threshold) for some predicates \\(P\\). Such predicates are called approximation resistant.  The main result of this article is as follows: a polynomial algorithm with some approximation ratio is obtained for the reoptimization of the problem Max-CSP-\\(P\\) in inserting some constraint. The ratio is shown to be the threshold ratio if the predicate \\(P\\) belongs to the class of approximation resistant predicates.''","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$357DF60F-71F0-4E90-B37F-3C4540FDE294","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"52de7d4bf5a27d5ad252804eec58396bb3e40c44","datavalue":{"value":"90C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q380664$AC73485F-6D9D-4D04-AE29-5AE9E67D2D06","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9829555f4073fc92047396e3e3c9b9d890b8d68e","datavalue":{"value":"6226969","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q380664$9568DE80-89C5-4007-81A0-A8997960A143","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd0fabe76e00454e555c49f402ec0e0f866e603d","datavalue":{"value":"reoptimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$25778ECE-1880-4538-9AAF-A038B117A6C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8850d9f2ca61e6022db5654ee12687888c4c1022","datavalue":{"value":"\\(C\\)-approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$CBCB31A2-01FD-409E-BD5F-5490E1945027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1f6541e1de301b0781910c1e6e57c223471cc98","datavalue":{"value":"discrete Fourier analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$278FA8AE-BAA1-4243-99E7-F415B8C5BA91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c94c4548a4129fc8b6cced20d5c03e5c3efda0","datavalue":{"value":"PCP theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$C0151CCB-E5AA-4C17-8395-4386AFB0F65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"587e9124c44be8f5161652b037d4ebd6be964f23","datavalue":{"value":"approximation resistant predicate","type":"string"},"datatype":"string"},"type":"statement","id":"Q380664$E8E60CD6-D4F4-47C8-B9B0-ED895D7B518D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5132ae210f55dd4ec071a1ba412ddaf1b39d04c3","datavalue":{"value":{"entity-type":"item","numeric-id":1090234,"id":"Q1090234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$9E47064A-D53E-4C13-AA23-66F8946766AC","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":"Q380664$DFC26B0F-884B-4CBD-B725-87D93DEF1F8C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78cc88da8f6f2e33ea95f263e7e072790603271e","datavalue":{"value":"https://doi.org/10.1007/s10559-012-9394-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q380664$492F6C62-059D-4F48-A969-5907AC5FB793","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3bfc35efdd3ca92f598131b5e9b512c84b8135b7","datavalue":{"value":"W1999144970","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q380664$63378FE6-8B72-45C8-8FEB-69F5566DC4C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0276a5091d47d933c6f800387f95d9445a47c9bf","datavalue":{"value":{"entity-type":"item","numeric-id":5757891,"id":"Q5757891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$7BE43B1D-BDBE-4BF2-8291-11DEF5873E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99de9dd37feefaa1ebaec9dd703223b3ae9d08a2","datavalue":{"value":{"entity-type":"item","numeric-id":2867366,"id":"Q2867366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$E6BF77D1-754C-41D0-895D-43A8BFA8B7AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91217a52b9aff6a0cdefac5319b4caefa82eab98","datavalue":{"value":{"entity-type":"item","numeric-id":4432763,"id":"Q4432763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$816DCF32-C069-4F5B-89B1-9D7096D2F5D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6ae0f3c49e94d09cd6277539fdef2d16da999a9","datavalue":{"value":{"entity-type":"item","numeric-id":608266,"id":"Q608266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$D1C9E515-B7A3-47D0-9749-5C816024D3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f1752c6678262d9ba0fedf23135d543033290af","datavalue":{"value":{"entity-type":"item","numeric-id":2906564,"id":"Q2906564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$60039B75-465E-47BB-84E2-4E2261EDEE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$51E75E19-5D58-4BB8-B23B-C4246A40DA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$6666F5B7-CF71-4D4A-83F7-F9AA7F03876E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed97d9cb381fa44bbd6ac9207fd7e4aa47354791","datavalue":{"value":{"entity-type":"item","numeric-id":3158513,"id":"Q3158513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$3DD7AD7A-0DC8-409F-B691-45D1410A3EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc39092484c42c2661962bc3a074cbc74d5b534e","datavalue":{"value":{"entity-type":"item","numeric-id":3158518,"id":"Q3158518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$DE89CD96-B111-44E2-B11B-FE8B1DF451C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0aeb7b6a9d849e663fb1717f079155c98337eba","datavalue":{"value":{"entity-type":"item","numeric-id":3546312,"id":"Q3546312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$968793F4-F55A-4AAA-B0C6-A680F1AA10BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7f992e855d8b9b42f253fc7f7d98a5e06e39cb4","datavalue":{"value":{"entity-type":"item","numeric-id":4369893,"id":"Q4369893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$1A8ADC7F-3E8F-41E9-A84A-546567E0F57F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39737725ea0d422db94ccf540c67892fa430a47c","datavalue":{"value":{"entity-type":"item","numeric-id":5479365,"id":"Q5479365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$78F75DE1-6DD5-4E74-8CBE-F98D75FF5566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf38d3aafe2ee0b4b6d9fb9a5d5f6717b92fa0ac","datavalue":{"value":{"entity-type":"item","numeric-id":4250183,"id":"Q4250183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$043DBBE8-2448-4F23-A532-D78B093BB6E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51a60583410113f671ac14914652a2f7012e5461","datavalue":{"value":{"entity-type":"item","numeric-id":5302081,"id":"Q5302081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$E7EC8E5D-C9EF-49D4-BEDB-36540B84FA5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db9bd384c5551eaec1fa0907ad767d3315ac19c6","datavalue":{"value":{"entity-type":"item","numeric-id":3096713,"id":"Q3096713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$C4201BF3-7C15-4F9E-8116-01C8A195CDB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7c1b8cc24016a7c6b464cd2135f72b919e9781","datavalue":{"value":{"entity-type":"item","numeric-id":4388898,"id":"Q4388898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$6F93B206-D3F8-47EC-8A7B-2B1C85B46D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8658e6d71d7258b809c478c332d93b25a4d9b43","datavalue":{"value":{"entity-type":"item","numeric-id":4782696,"id":"Q4782696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$58429026-2A15-4BDA-9F92-B91C2FE27271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8232dd8a3466a7a42f6665aa7fabea01ebe9b6","datavalue":{"value":{"entity-type":"item","numeric-id":1957000,"id":"Q1957000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$F3954EC4-1C68-4D9A-9F16-957F81D2FC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfffed3b8aef775b89adac6380bed4ddec7e24e1","datavalue":{"value":{"entity-type":"item","numeric-id":2247803,"id":"Q2247803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q380664$496AC9D7-2143-494F-BD4F-20C0EFD5D611","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e21e01984da07bdae7f06e9f6f57ebbef825fe1d","datavalue":{"value":"10.1007/S10559-012-9394-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q380664$EFB95E11-BE96-4BFA-A1BA-088FF3FCC738","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c008bed4c9dbe68c6185edcc9a7844b61b150861","datavalue":{"value":{"entity-type":"item","numeric-id":2850118,"id":"Q2850118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a57bb713c35c37b6c935e92c89624bac68bc8ddc","datavalue":{"value":{"amount":"+0.85584956407547","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":"Q380664$4547F1FB-9459-43D9-AC0C-D15C3FD06B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08a5171ba5b4c22745cddd87113c79f773987ab4","datavalue":{"value":{"entity-type":"item","numeric-id":4899322,"id":"Q4899322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab51b730611f11323cf089941611c74643d82a8","datavalue":{"value":{"amount":"+0.8547349572181702","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":"Q380664$FE538995-6B84-47EF-B2A9-959B0F1409F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"802fec7cd967c013d0ebba5d809cd1885939ac50","datavalue":{"value":{"entity-type":"item","numeric-id":5479365,"id":"Q5479365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27c671d72c069638b853eb323f5dabeb02863dd0","datavalue":{"value":{"amount":"+0.7754331827163696","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":"Q380664$425221BA-EA0B-4FC5-B894-22279E3AC063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2e2ecb043f7dfde1d7a807290e1f27d23bf3083","datavalue":{"value":{"entity-type":"item","numeric-id":466363,"id":"Q466363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2fe884e7f9b19c6599cda04fbe9f4740448f6f8","datavalue":{"value":{"amount":"+0.7682071924209595","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":"Q380664$C3DC5A3E-07C9-4E11-9947-28C423F43630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"168ef47b65a84e30561543699101ac65017ec3b8","datavalue":{"value":{"entity-type":"item","numeric-id":2850154,"id":"Q2850154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a1c940c64f91f0c6158c8f72d87ef3a05da79e2","datavalue":{"value":{"amount":"+0.7665148973464966","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":"Q380664$B00753B6-8002-4093-97E3-E132E66F0795","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reoptimization of constraint satisfaction problems with approximation resistant predicates","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reoptimization_of_constraint_satisfaction_problems_with_approximation_resistant_predicates"}}}}}