Summary
This research looks at a type of problem where you want to make certain choices to satisfy the most weighted conditions, but you can only pick a limited number of options. The authors fully describe which kinds of Boolean constraint sets allow for fast approximation algorithms that work well when you consider both how many things you can pick and how complicated each condition is. They identify two special structural properties of constraints, called Direct and Rooted, that make getting close to the best solution computationally feasible. If the problem doesn’t have these properties, then a fast good-approximation algorithm likely doesn’t exist unless some major complexity assumptions fail.
What this means in practice
- •For optimization software developers: Design approximation algorithms for constraint maximization problems with cardinality limits using the identified structural conditions for better efficiency.
- •For network resource managers: Use the classification to understand when approximate solutions to resource allocation with limited active nodes are feasible.
A theory result. No direct application yet.
Abstract
We study \textsc{Max $k$-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most $k$ variables to $1$. Each constraint uses at most $d$ distinct variables and a relation from a finite Boolean language $Γ$. This includes \textsc{Partial Vertex Cover}, \textsc{Densest $k$-Subgraph}, bounded-frequency \textsc{Maximum Coverage}, and cardinality-constrained \textsc{Max-SAT}. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter $k+d$. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a \emph{unit witness} if the tuple with a single $1$ in that coordinate is accepted, and a \emph{control} otherwise. A relation is \emph{Direct} if setting any selected control to $0$, with all other coordinates unchanged, preserves satisfaction. It is \emph{Rooted} if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to $0$, and setting any subset of selected controls to $0$ preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic $(1-\varepsilon)$-approximation for every rational $\varepsilon\in(0,1)$ in time $2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}$, where $\ell_{\mathrm{in}}$ is the total input length. The algorithms are uniform in $d$ and give an EPAS parameterized by $k+d$ whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless $\mathsf{FPT}=\mathsf{W[1]}$, even for unweighted instances where no two constraints involve the same set of variables.