Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909633778548736 |
|---|---|
| author | Austrin, Per Bercea, Ioana O. Goswami, Mayank Limaye, Nutan Srinivasan, Adarsh |
| author_facet | Austrin, Per Bercea, Ioana O. Goswami, Mayank Limaye, Nutan Srinivasan, Adarsh |
| contents | Given a $k$-CNF formula and an integer $s$, we study algorithms that obtain $s$ solutions to the formula that are maximally dispersed. For $s=2$, the problem of computing the diameter of a $k$-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for $k=2$. Assuming SETH, the current best upper bound [Angelsmark and Thapper '04] goes to $4^n$ as $k \rightarrow \infty$. As our first result, we give exact algorithms for using the Fast Fourier Transform and clique-finding that run in $O^*(2^{(s-1)n})$ and $O^*(s^2 |Ω_{F}|^{ω\lceil s/3 \rceil})$ respectively, where $|Ω_{F}|$ is the size of the solution space of the formula $F$ and $ω$ is the matrix multiplication exponent.
As our main result, we re-analyze the popular PPZ (Paturi, Pudlak, Zane '97) and Schöning's ('02) algorithms (which find one solution in time $O^*(2^{\varepsilon_{k}n})$ for $\varepsilon_{k} \approx 1-Θ(1/k)$), and show that in the same time, they can be used to approximate the diameter as well as the dispersion ($s>2$) problems. While we need to modify Schöning's original algorithm, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe that this property may be of independent interest.
Finally, we present algorithms to output approximately diverse, approximately optimal solutions to NP-complete optimization problems running in time $\text{poly}(s)O^*(2^{\varepsilon n})$ with $\varepsilon<1$ for several problems such as Minimum Hitting Set and Feedback Vertex Set. For these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions $s$. Our methods find bi-approximations with polynomial dependence on $s$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03465 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments Austrin, Per Bercea, Ioana O. Goswami, Mayank Limaye, Nutan Srinivasan, Adarsh Computational Complexity Data Structures and Algorithms Given a $k$-CNF formula and an integer $s$, we study algorithms that obtain $s$ solutions to the formula that are maximally dispersed. For $s=2$, the problem of computing the diameter of a $k$-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for $k=2$. Assuming SETH, the current best upper bound [Angelsmark and Thapper '04] goes to $4^n$ as $k \rightarrow \infty$. As our first result, we give exact algorithms for using the Fast Fourier Transform and clique-finding that run in $O^*(2^{(s-1)n})$ and $O^*(s^2 |Ω_{F}|^{ω\lceil s/3 \rceil})$ respectively, where $|Ω_{F}|$ is the size of the solution space of the formula $F$ and $ω$ is the matrix multiplication exponent. As our main result, we re-analyze the popular PPZ (Paturi, Pudlak, Zane '97) and Schöning's ('02) algorithms (which find one solution in time $O^*(2^{\varepsilon_{k}n})$ for $\varepsilon_{k} \approx 1-Θ(1/k)$), and show that in the same time, they can be used to approximate the diameter as well as the dispersion ($s>2$) problems. While we need to modify Schöning's original algorithm, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe that this property may be of independent interest. Finally, we present algorithms to output approximately diverse, approximately optimal solutions to NP-complete optimization problems running in time $\text{poly}(s)O^*(2^{\varepsilon n})$ with $\varepsilon<1$ for several problems such as Minimum Hitting Set and Feedback Vertex Set. For these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions $s$. Our methods find bi-approximations with polynomial dependence on $s$. |
| title | Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.03465 |