<p>Given <span class="math-container">$A\in\Bbb Z^{n\times k}$</span>, <span class="math-container">$v\in\Bbb Z^n$</span> and variables <span class="math-container">$x_1,\dots,x_k$</span> given as a vector <span class="math-container">$x$</span> we know that solving <span class="math-container">$x\in\Bbb Z^k$</span> in <span class="math-container">$Ax\leq v$</span> is fixed parameter tractable. There is a deterministic algorithm that runs in <span class="math-container">$k^{O(k)}\mathsf{poly(nL)})$</span> time for some <span class="math-container">$c&gt;0$</span> where <span class="math-container">$L$</span> is number of bits to represent the problem.</p>
<p>What is the space complexity of the algorithm? Does it run in <span class="math-container">$\mathsf{poly}(nk\log L)$</span> space?</p>

<integer-programming><space-complexity>
Space complexity of integer programming
Turbo
# Space complexity of integer programming

(Asked by: username_0 on 2017-02-26)

Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x\_1,\dots,x\_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a deterministic algorithm that runs in $k^{O(k)}\mathsf{poly(nL)})$ time for some $c>0$ where $L$ is number of bits to represent the problem.

What is the space complexity of the algorithm? Does it run in $\mathsf{poly}(nk\log L)$ space?

**Tags:** integer-programming, space-complexity

---

## 0 answers

