A global convexity analysis on the MAX-SAT domain Export

@inproceedings{citeulike:4834517, abstract = {To this day, there is little theoretical understanding on the mechanics of local search algorithms and metaheuristics. Therefore, this work studies the solution space of random MAX-SAT, which is a SAT variant. This analysis is focused on the study of global convexity, which may be exploited by some metaheuristics, as already observed in the literature. Understanding the structure of the solution space will give more insight on metaheuristics effectiveness for MAX-SAT. This paper presents experimental results suggesting that random MAX-SAT is not globally convex, except for some overconstrained instances. Consequently, for the latter case, it is possible to predict that a population-based meta-heuristic would be able to defeat an efficient local search algorithm, as experimentally proven in this work.}, author = {Villagra, M. and Baran, B.}, booktitle = {Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd}, citeulike-article-id = {4834517}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/BIMNICS.2007.4610085}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4610085}, doi = {10.1109/BIMNICS.2007.4610085}, journal = {Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd}, keywords = {convexity, global, sat}, pages = {74--78}, posted-at = {2009-06-13 09:28:04}, priority = {0}, title = {A global convexity analysis on the MAX-SAT domain}, url = {http://dx.doi.org/10.1109/BIMNICS.2007.4610085}, year = {2007} }

TY - CONF ID - citeulike:4834517 L3 - citeulike-article-id:4834517 N2 - To this day, there is little theoretical understanding on the mechanics of local search algorithms and metaheuristics. Therefore, this work studies the solution space of random MAX-SAT, which is a SAT variant. This analysis is focused on the study of global convexity, which may be exploited by some metaheuristics, as already observed in the literature. Understanding the structure of the solution space will give more insight on metaheuristics effectiveness for MAX-SAT. This paper presents experimental results suggesting that random MAX-SAT is not globally convex, except for some overconstrained instances. Consequently, for the latter case, it is possible to predict that a population-based meta-heuristic would be able to defeat an efficient local search algorithm, as experimentally proven in this work. JF - Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd EP - 78 TI - A global convexity analysis on the MAX-SAT domain T2 - Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd SP - 74 KW - convexity KW - global KW - sat AU - Villagra, M AU - Baran, B PY - 2007/// UR - http://dx.doi.org/10.1109/BIMNICS.2007.4610085 ER -