Approximation Strategies for Incomplete MaxSAT

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

Preview

Text 1806.07164v1.pdf - Submitted Version Download (208kB) | Preview

Abstract

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 Creators ORCiD Joshi, Saurabh UNSPECIFIED
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
URI:	http://raiithold.iith.ac.in/id/eprint/4198
Publisher URL:	https://arxiv.org/abs/1806.07164
Related URLs:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item