8 Result(s)
within
Chu-Min Li
Algorithm Analysis and Problem Complexity
Artificial Intelligence
-
Chapter and Conference Paper
Incremental MaxSAT Reasoning to Reduce Branches in a Branch-and-Bound Algorithm for MaxClique
When searching for a maximum clique of a graph using a branch-and-bound algorithm, it is usually believed that one should minimize the set of branching vertices from which search is necessary. It this paper, w...
-
Chapter and Conference Paper
Exploiting Historical Relationships of Clauses and Variables in Local Search for Satisfiability
Variable properties such as score and age are used to select a variable to flip. The score of a variable x refers to the decrease in the number of unsatisfied clauses if x is flipped. The age of x refers to the n...
-
Chapter and Conference Paper
Satisfying versus Falsifying in Local Search for Satisfiability
During local search, clauses may frequently be satisfied or falsified. Modern SLS algorithms often exploit the falsifying history of clauses to select a variable to flip, together with variable properties such...
-
Chapter and Conference Paper
Analyzing the Instances of the MaxSAT Evaluation
The MaxSAT Evaluation [1] is an affiliated event of the SAT Conference that is held every year since 2006, and is devoted to empirically evaluate exact MaxSAT algorithms solving any of the following problems: ...
-
Chapter and Conference Paper
Exploiting Cycle Structures in Max-SAT
We investigate the role of cycles structures (i.e., subsets of clauses of the form $\bar{l}_{1}\vee l_{2}, \bar{l}_{1}\vee l_{3},\bar{...
-
Chapter and Conference Paper
A Preprocessor for Max-SAT Solvers
We describe a preprocessor that incorporates a variable saturation procedure for Max-SAT, and provide empirical evidence that it improves the performance of some of the most successful state-of-the-art solvers...
-
Chapter and Conference Paper
Combining Adaptive Noise and Look-Ahead in Local Search for SAT
The adaptive noise mechanism was introduced in Novelty+ to automatically adapt noise settings during the search [4]. The local search algorithm G 2 WSAT deterministically exploits prom...
-
Chapter and Conference Paper
Diversification and Determinism in Local Search for Satisfiability
The choice of the variable to flip in the Walksat family procedures is always random in that it is selected from a randomly chosen unsatisfied clause c. This choice in Novelty or R-Novelty heuristics also contain...
