2026-08-08T15:18:03Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:20720 2024-08-29T08:52:52Z ddc:004 open_access
On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper) de Vlas, Jorke M. constraint satisfaction problems integer programming CSP dichotomy We give a polynomial time algorithm that solves a CSP over 𝐙 with linear inequalities of the form c^{a₁} x - c^{aβ‚‚} y ≀ b where x and y are variables, a₁, aβ‚‚ and b are parameters, and c is a fixed constant. This is a step in classifying the complexity of CSP(Ξ“) for first-order reducts Ξ“ from (𝐙, < ,+,1). The algorithm works by first reducing the infinite domain to a finite domain by inferring an upper bound on the size of the smallest solution, then repeatedly merging consecutive constraints into new constraints, and finally solving the problem using arc consistency. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Jorke M. de Vlas 2024 Is Part Of LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2024.35 urn:nbn:de:0030-drops-207203 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode