4 papers · 1 filter
Optimal FPT-Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-appro…
Parameterized Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the Min--Lin problem: given a system of length- linear equations modulo , find of minimum cardinality such that is satisfiable…
Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas +1
We study a model of constraint satisfaction problems geared towards instances with few variables but with domain of unbounded size (udCSP). Our model is inspired by recent work on…
Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable.…