Weight Redistribution for Unweighted MAX-SAT

File Size Format
49557_1.pdf 183Kb Adobe PDF View
Title Weight Redistribution for Unweighted MAX-SAT
Author Ishtaiwi, Abdelraouf; Thornton, John Richard; Sattar, Abdul
Publication Title AI 2007: Advances in Artificial Intelligence
Editor Mehmet A. Orgun, John Thornton
Year Published 2007
Place of publication Berlin, Germany
Publisher Springer
Abstract Many real-world problems are over-constrained and require search techniques adapted to optimising cost functions rather than search- ing for consistency. This makes the MAX-SAT problem an important area of research for the satis¯ability (SAT) community. In this study we perform an empirical analysis of several of the best performing SAT local search techniques in the domain of unweighted MAX-SAT. In particular, we test two of the most recently developed SAT clause weight redistri- bution algorithms, DDFW and DDFW+, against three more well-known techniques (RSAPS, AdaptNovelty+ and PAWS). Based on an empir- ical study across a range of previously studied problems we conclude that DDFW is the most promising algorithm in terms of robust average performance.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.cit.gu.edu.au/conferences/austai/
Alternative URI http://www.springer.com/computer/artificial/book/978-3-540-76926-2
Copyright Statement Copyright 2007 Springer. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com.
ISBN 978-3-540-76926-2
Conference name 20th Australian Joint Conference on Artificial Intelligence
Location Gold Coast, Queensland, Australia
Date From 2007-12-02
Date To 2007-12-06
URI http://hdl.handle.net/10072/18346
Date Accessioned 2008-03-01
Date Available 2008-11-19T02:56:30Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Other Artificial Intelligence
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Brief Record

Griffith University copyright notice