3 papers
cs.DS2024
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.…
cs.CC2024
CSPs with Few Alien Constraints
Peter Jonsson, Victor Lagerkvist, George Osipov
The constraint satisfaction problem asks to decide if a set of constraints over a relational structure is satisfiable (CSP). We consider CSP$(\mathcal{…
cs.DS2022
Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an a…