Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • 3
    $\begingroup$ @Nathaniel Well, the first paragraph was more intended as an apology than an accusation, though it may not have come across that way. I mostly wanted to stress that (to the best of my knowledge) most CS courses don't cover this because you would have to follow a more specialized course that's usually not in a CS curriculum. $\endgroup$ Commented Jan 17, 2024 at 20:23
  • 1
    $\begingroup$ I did not take this as an accusation, don't worry. I understand perfectly that such a proof is not covered in a CS course, but I found it unfortunate not to have references to further explainations. $\endgroup$ Commented Jan 17, 2024 at 20:32
  • 1
    $\begingroup$ I tried to understand the proof of the property. After a bit of browsing, I gave up. Here is the dependancy graph of the different theorems and properties necessary to understand the whole proof… i.sstatic.net/AtIew.png $\endgroup$ Commented Jan 18, 2024 at 23:05
  • 1
    $\begingroup$ Elaborating on the rough sketch of proof: Any vertex on the polyhedron of rational solutions to the LP relaxation of the ILP is the solution to a linear equation system with coefficients from the ILP, so it can be expressed exactly using Cramer's rule, and we can bound the number of bits in the numerator and denominator: both are polynomial in the size of the ILP. Hence the same holds for the coordinates of the bounding box of the vertices; if the polyhedron is bounded, we're done. If the polyhedron is unbounded, things get trickier. (Continued) $\endgroup$ Commented Jan 20, 2024 at 7:28
  • 1
    $\begingroup$ For an unbounded polyhedron, it is possible that the smallest integer point is much farther out than any rational vertex; how much farther depends (informally speaking) on how wide an angle the polyhedron (polyhedral cone?) covers. So this is where the rays enter the picture… (I'm not surprised that needs a ton of machinery to work through.) And having some solution matters. $1 \leqslant 3x_1 - 3x_2 \leqslant 2$ where $x_1,x_2 \geqslant 0$ is rationally feasible, but lacks integer solutions. $\endgroup$ Commented Jan 20, 2024 at 7:44