Approximation Strategies for Incomplete MaxSAT

Joshi, Saurabh and Kumar, Prateek and Martins, Ruben and Rao, Sukrut (2018) Approximation Strategies for Incomplete MaxSAT. In: ., ., .. (Unpublished)

1806.07164v1.pdf - Submitted Version

Download (208kB) | Preview


Incomplete MaxSAT solving aims to quickly find a solution that attempts to minimize the sum of the weights of the unsati sfied soft clauses without providing any optimality guarantees. In th is paper, we propose two approximation strategies for improving incomp lete MaxSAT solving. In one of the strategies, we cluster the weights and approximate them with a representative weight. In another strategy, we b reak up the problem of minimizing the sum of weights of unsatisfiable clauses into multiple minimization subproblems. Experimental res ults show that approximation strategies can be used to find better solution s than the best incomplete solvers in the MaxSAT Evaluation 2017.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 06 Jul 2018 04:30
Last Modified: 06 Jul 2018 04:30
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4198 Statistics for this ePrint Item