arXiv preprint ·
On Diverse Solutions to Max-k-CSP and Bounded Degree k-SAT
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the problem of generating diverse solutions to Max-$k$-CSP and bounded-degree $k$-SAT, focusing on two distinct metrics: constraint diversity and variable diversity. For constraint diversity, the goal is to output $s \geq 2$ assignments to the CSP such that each assignment satisfies a $c$-fraction of the constraints, while maximizing the diversity among the $0$-$1$ indicator vectors of satisfied constraints in the Hamming metric. By reducing this to a multi-criteria optimization problem, we design $poly(n,s)$ time approximation algorithms that return s assignments achieving provable bi-criteria guarantees on both the fraction of satisfied constraints and diversity of the constraint vectors. For variable diversity, the objective is to maximize the Hamming distance between the assignments, while also maximizing the number of constraints satisfied. For Max-$k$-CSP instances when the desired number of solutions is $s=2^{O(n)}$, we implicitly represent these diverse approximate solutions by constructing linear codes within the solution space. Finally, we investigate variable diversity for $k$-SAT in the Lovász Local Lemma regime. In this setting, we establish NP-hardness for the exact diversity problem (computing the diameter of the solution space) and provide a polynomial-time approximation algorithm to efficiently generate diverse satisfying assignments.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
On the Guo-Fang-Lu Algorithm for Komlos Discrepancy
Online Stochastic Allocation with Increasing Returns
On the Complexity of Forcing and Anti-Forcing Minimum Cuts
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.