DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.CP.2024.35

On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper)

Authors: Jorke M. de Vlas

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

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.

Cite as

Jorke M. de Vlas. On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 35:1-35:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{devlas:LIPIcs.CP.2024.35,
  author =	{de Vlas, Jorke M.},
  title =	{{On the Complexity of Integer Programming with Fixed-Coefficient Scaling}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{35:1--35:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.35},
  URN =		{urn:nbn:de:0030-drops-207203},
  doi =		{10.4230/LIPIcs.CP.2024.35},
  annote =	{Keywords: constraint satisfaction problems, integer programming, CSP dichotomy}
}

Search Results

Documents authored by de Vlas, Jorke M.

On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message