2026-07-22T00:13:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18491 2024-03-06T11:02:02Z ddc:004 open_access

LS-DTKMS: A Local Search Algorithm for Diversified Top-k MaxSAT Problem Zhou, Junping Liang, Jiaxin Yin, Minghao He, Bo Top-k MaxSAT local search The Maximum Satisfiability (MaxSAT), an important optimization problem, has a range of applications, including network routing, planning and scheduling, and combinatorial auctions. Among these applications, one usually benefits from having not just one single solution, but k diverse solutions. Motivated by this, we study an extension of MaxSAT, named Diversified Top-k MaxSAT (DTKMS) problem, which is to find k feasible assignments of a given formula such that each assignment satisfies all hard clauses and all of them together satisfy the maximum number of soft clauses. This paper presents a local search algorithm, LS-DTKMS, for DTKMS problem, which exploits novel scoring functions to select variables and assignments. Experiments demonstrate that LS-DTKMS outperforms the top-k MaxSAT based DTKMS solvers and state-of-the-art solvers for diversified top-k clique problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Junping Zhou and Jiaxin Liang and Minghao Yin and Bo He 2023 Is Part Of LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAT.2023.29 urn:nbn:de:0030-drops-184912 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode