跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.17951 · v1

Parameterized Approximation for Minimizing Uncovered Elements and Unsatisfied Constraints

首次提交 2026-11-13 17:40
版本更新 2026-11-13 17:40
雷达观测 2026-11-16 11:42
arXiv ↗PDF ↗

摘要

Min-UnCoverage asks for at most kk sets minimizing uncovered weight. Min-Unsat SAT and Min-Unsat CSP ask for an assignment with at most kk true variables minimizing the weight of unsatisfied clauses or constraints. For constraints of arity at most dd, we give a deterministic (1+ε)(1+\varepsilon)-approximation for weighted Min-Unsat CSP in (dk/ε)O(k)NO(1)(dk/\varepsilon)^{O(k)}N^{O(1)} time, where NN is the input size. This also gives approximation schemes for bounded-arity SAT and coverage with bounded element frequency. We show that weighted coverage with set size at most dd can be solved exactly in 2O(kd)NO(1)2^{O(kd)}N^{O(1)} time by adapting color-coding. For coverage on incidence graphs of bounded semi-ladder index, we give a deterministic parameterized approximation scheme . We show that, unless FPT=W[1]\mathrm{FPT}=\mathrm{W}[1], SAT and CSP have no finite-factor FPT approximation parameterized by k+dk+d when variable frequency is at most dd, or on K3,3K_{3,3}-free incidence graphs of semi-ladder index at most four. Known Hitting Set hardness gives the same lower bound for all three problems at VC dimension two. Under the same assumption, we show that no computable relaxation g(k,d)≥kg(k,d)\geq k allows an FPT algorithm to preserve a prescribed unsatisfied-weight target for SAT or CSP, already for arity three and, separately, bounded variable frequency. For coverage, known algorithms preserve the target using at most k+1k+1 sets on incidence graphs of bounded semi-ladder index.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-13 17:40 · 最新观测版本

Parameterized Approximation for Minimizing Uncovered Elements and Unsatisfied Constraints

Min-UnCoverage asks for at most kk sets minimizing uncovered weight. Min-Unsat SAT and Min-Unsat CSP ask for an assignment with at most kk true variables minimizing the weight of unsatisfied clauses or constraints. For constraints of arity at most dd, we give a deterministic (1+ε)(1+\varepsilon)-approximation for weighted Min-Unsat CSP in (dk/ε)O(k)NO(1)(dk/\varepsilon)^{O(k)}N^{O(1)} time, where NN is the input size. This also gives approximation schemes for bounded-arity SAT and coverage with bounded element frequency. We show that weighted coverage with set size at most dd can be solved exactly in 2O(kd)NO(1)2^{O(kd)}N^{O(1)} time by adapting color-coding. For coverage on incidence graphs of bounded semi-ladder index, we give a deterministic parameterized approximation scheme . We show that, unless FPT=W[1]\mathrm{FPT}=\mathrm{W}[1], SAT and CSP have no finite-factor FPT approximation parameterized by k+dk+d when variable frequency is at most dd, or on K3,3K_{3,3}-free incidence graphs of semi-ladder index at most four. Known Hitting Set hardness gives the same lower bound for all three problems at VC dimension two. Under the same assumption, we show that no computable relaxation g(k,d)≥kg(k,d)\geq k allows an FPT algorithm to preserve a prescribed unsatisfied-weight target for SAT or CSP, already for arity three and, separately, bounded variable frequency. For coverage, known algorithms preserve the target using at most k+1k+1 sets on incidence graphs of bounded semi-ladder index.

查看此版本解读 →查看此版本原文 ↗