Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.06335 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929372603088896 |
|---|---|
| author | Manurangsi, Pasin |
| author_facet | Manurangsi, Pasin |
| contents | In the Max $k$-Weight SAT (aka Max SAT with Cardinality Constraint) problem, we are given a CNF formula with $n$ variables and $m$ clauses together with a positive integer $k$. The goal is to find an assignment where at most $k$ variables are set to one that satisfies as many constraints as possible. Recently, Jain et al. [SODA'23] gave an FPT approximation scheme (FPT-AS) with running time $2^{O\left(\left(dk/ε\right)^d\right)} \cdot (n + m)^{O(1)}$ for Max $k$-Weight SAT when the incidence graph is $K_{d,d}$-free. They asked whether a polynomial-size approximate kernel exists. In this work, we answer this question positively by giving an $(1 - ε)$-approximate kernel with $\left(\frac{d k}ε\right)^{O(d)}$ variables. This also implies an improved FPT-AS with running time $(dk/ε)^{O(dk)} \cdot (n + m)^{O(1)}$. Our approximate kernel is based mainly on a couple of greedy strategies together with a sunflower lemma-style reduction rule. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06335 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back Manurangsi, Pasin Data Structures and Algorithms In the Max $k$-Weight SAT (aka Max SAT with Cardinality Constraint) problem, we are given a CNF formula with $n$ variables and $m$ clauses together with a positive integer $k$. The goal is to find an assignment where at most $k$ variables are set to one that satisfies as many constraints as possible. Recently, Jain et al. [SODA'23] gave an FPT approximation scheme (FPT-AS) with running time $2^{O\left(\left(dk/ε\right)^d\right)} \cdot (n + m)^{O(1)}$ for Max $k$-Weight SAT when the incidence graph is $K_{d,d}$-free. They asked whether a polynomial-size approximate kernel exists. In this work, we answer this question positively by giving an $(1 - ε)$-approximate kernel with $\left(\frac{d k}ε\right)^{O(d)}$ variables. This also implies an improved FPT-AS with running time $(dk/ε)^{O(dk)} \cdot (n + m)^{O(1)}$. Our approximate kernel is based mainly on a couple of greedy strategies together with a sunflower lemma-style reduction rule. |
| title | Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.06335 |