{"data":{"id":"10.48550/arxiv.1401.3483","type":"dois","attributes":{"doi":"10.48550/arxiv.1401.3483","prefix":"10.48550","suffix":"arxiv.1401.3483","identifiers":[{"identifier":"1401.3483","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1401.3483"}],"creators":[{"name":"Chieu, Hai Leong","nameType":"Personal","givenName":"Hai Leong","familyName":"Chieu","affiliation":[],"nameIdentifiers":[]},{"name":"Lee, Wee Sun Sun","nameType":"Personal","givenName":"Wee Sun Sun","familyName":"Lee","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem"}],"publisher":"arXiv","container":{},"publicationYear":2014,"subjects":[{"lang":"en","subject":"Artificial Intelligence (cs.AI)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2014-01-15T05:36:10Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2014-01-16T01:06:16Z","dateType":"Updated","dateInformation":"v1"},{"date":"2014-01","dateType":"Available","dateInformation":"v1"},{"date":"2014","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1613/jair.2808","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNDAxLjM0ODM8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xNDAxLjM0ODM8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Q2hpZXUsIEhhaSBMZW9uZzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+SGFpIExlb25nPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkNoaWV1PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkxlZSwgV2VlIFN1biBTdW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPldlZSBTdW4gU3VuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkxlZTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+UmVsYXhlZCBTdXJ2ZXkgUHJvcGFnYXRpb24gZm9yIFRoZSBXZWlnaHRlZCBNYXhpbXVtIFNhdGlzZmlhYmlsaXR5IFByb2JsZW08L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTQ8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5BcnRpZmljaWFsIEludGVsbGlnZW5jZSAoY3MuQUkpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxNC0wMS0xNVQwNTozNjoxMFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxNC0wMS0xNlQwMTowNjoxNlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE0LTAxPC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJUZXh0Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHJlbGF0ZWRJZGVudGlmaWVycz4KICAgIDxyZWxhdGVkSWRlbnRpZmllciByZWxhdGVkSWRlbnRpZmllclR5cGU9IkRPSSIgcmVsYXRpb25UeXBlPSJJc1ZlcnNpb25PZiI+MTAuMTYxMy9qYWlyLjI4MDg8L3JlbGF0ZWRJZGVudGlmaWVyPgogIDwvcmVsYXRlZElkZW50aWZpZXJzPgogIDx2ZXJzaW9uPjE8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9ub25leGNsdXNpdmUtZGlzdHJpYi8xLjAvIj5hclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2U8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5UaGUgc3VydmV5IHByb3BhZ2F0aW9uIChTUCkgYWxnb3JpdGhtIGhhcyBiZWVuIHNob3duIHRvIHdvcmsgd2VsbCBvbiBsYXJnZSBpbnN0YW5jZXMgb2YgdGhlIHJhbmRvbSAzLVNBVCBwcm9ibGVtIG5lYXIgaXRzIHBoYXNlIHRyYW5zaXRpb24uIEl0IHdhcyBzaG93biB0aGF0IFNQIGVzdGltYXRlcyBtYXJnaW5hbHMgb3ZlciBjb3ZlcnMgdGhhdCByZXByZXNlbnQgY2x1c3RlcnMgb2Ygc29sdXRpb25zLiBUaGUgU1AteSBhbGdvcml0aG0gZ2VuZXJhbGl6ZXMgU1AgdG8gd29yayBvbiB0aGUgbWF4aW11bSBzYXRpc2ZpYWJpbGl0eSAoTWF4LVNBVCkgcHJvYmxlbSwgYnV0IHRoZSBjb3ZlciBpbnRlcnByZXRhdGlvbiBvZiBTUCBkb2VzIG5vdCBnZW5lcmFsaXplIHRvIFNQLXkuIEluIHRoaXMgcGFwZXIsICB3ZSBmb3JtdWxhdGUgdGhlIHJlbGF4ZWQgc3VydmV5IHByb3BhZ2F0aW9uIChSU1ApIGFsZ29yaXRobSwgd2hpY2ggZXh0ZW5kcyB0aGUgU1AgYWxnb3JpdGhtIHRvIGFwcGx5IHRvIHRoZSAgd2VpZ2h0ZWQgTWF4LVNBVCBwcm9ibGVtLiBXZSBzaG93IHRoYXQgUlNQIGhhcyBhbiBpbnRlcnByZXRhdGlvbiBvZiAgZXN0aW1hdGluZyBtYXJnaW5hbHMgb3ZlciBjb3ZlcnMgdmlvbGF0aW5nIGEgc2V0IG9mIGNsYXVzZXMgd2l0aCAgbWluaW1hbCB3ZWlnaHQuIFRoaXMgbmF0dXJhbGx5IGdlbmVyYWxpemVzIHRoZSBjb3ZlciAgaW50ZXJwcmV0YXRpb24gb2YgU1AuIEVtcGlyaWNhbGx5LCB3ZSBzaG93IHRoYXQgUlNQIG91dHBlcmZvcm1zICBTUC15IGFuZCBvdGhlciBzdGF0ZS1vZi10aGUtYXJ0IE1heC1TQVQgc29sdmVycyBvbiByYW5kb20gTWF4LVNBVCBpbnN0YW5jZXMuIFJTUCBhbHNvIG91dHBlcmZvcm1zIHN0YXRlLW9mLXRoZS1hcnQgd2VpZ2h0ZWQgTWF4LVNBVCBzb2x2ZXJzIG9uIHJhbmRvbSB3ZWlnaHRlZCBNYXgtU0FUIGluc3RhbmNlcy48L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1401.3483","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-10T05:10:24.000Z","registered":"2022-03-10T05:10:25.000Z","published":"2014","updated":"2025-05-27T22:13:04.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1401.3483","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}