Revision as of 12:24, 27 April 2025 edit Al-Quaknaa (talk \| contribs) 27 edits →No dependence on input numbers in fixed dimension?: new section Tag: New topic ← Previous edit		Latest revision as of 12:25, 27 April 2025 edit undo Al-Quaknaa (talk \| contribs) 27 edits m →No dependence on input numbers in fixed dimension?
Line 25: == No dependence on input numbers in fixed dimension? == The article includes the following sentence: "Doignon's theorem asserts that an integer program is feasible whenever every subset of $''2^n$'' constraints is feasible; a method combining this result with algorithms for LP-type problems can be used to solve integer programs in time that is linear in ''m'' and fixed-parameter tractable (FPT) in ''n'', but possibly doubly exponential in ''n'', '''with no dependence on ''V''.'''" (emphasis in the end mine) I'm skeptical of this, and I couldn't find exactly this statement in the cited reference. If I'm wrong, the reference should contain a pointer to a specific statement. Why I think the claim does not hold: computing the gcd can be encoded as an ILP in 2 variables, and computing the gcd in any reasonable model takes non-constant number of operations (https://dl.acm.org/doi/abs/10.1145/103516.103522). So, what is meant here? [[User:Al-Quaknaa\|Martin Koutecký]] ([[User talk:Al-Quaknaa\|talk]]) 12:24, 27 April 2025 (UTC)

Talk:Integer programming: Difference between revisions