Polynomial time certifying algorithms for the planar quantified integer programming problem
This article is concerned with the design and analysis of polynomial time algorithms for determining whether a Planar Quantified Integer Program (PQIP) is feasible. A PQIP can be described briefly as an integer program involving two variables, in which each variable can be either universally or existentially quantified. There are four types of PQIPs, depending on how the variables are quantified (existentially or universally). In this article, we present two new, simple, and efficient algorithms for the for all there exists case as well as a detailed account of the complexity of the other cases. Moreover, we discuss certification with respect to the provided algorithms.
polynomial time certifying algorithms quantified integer programs constraints lattice points