Integer programming

[2/50%]

Show

LaTeX

Show LaTeX

Problem 7.1.8 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 7.1 "NP"

(a)(b)(c)(d)

Let $A$ be an $n \times n$ integer matrix, and $b$ an $n$ -dimensional integer vector. Let $\alpha$ be the maximum absolute value of integers in $A$ and $b$ , and $q= \max \left\{ m, n\right\}$ .

(a)

Show that if $B$ is a square submatrix of $A$ , then $\left|\operatorname {det}(B)\right| \leq (\alpha q)^{q}$ , where $\operatorname {det}(B)$ denotes the determinant of matrix $B$ .

(b)

Show that if $\operatorname {rank}(A)=r<m$ , then there exists a nonzero vector $z$ such that $A z=0$ and the maximum absolute value of integers in $z$ is bounded by $(\alpha q)^{q}$ .

(c)

Assume that $A x \geq b$ has an integer solution $x$ . Let $a_{i}$ denote the $i$ th row of $A, b_{i}$ the $i$ th component of $b$ , and $e_{j}$ the $j$ th $m$ dimensional unit vector (i.e., all components of $e_{j}$ is 0, except that the $j$ th component is 1). Let $x$ be a solution for $A x \geq b$ that maximizes the number of elements in the following set:

\begin{aligned} \mathcal{A}_{x}= & \left\{ a_{i} \mid b_{i} \leq a_{i} x \leq b_{i}+(\alpha q)^{q+1}, 1 \leq i \leq n\right\} \\ & \cup \left\{ e_{j} \mid \left|x_{j}\right| \leq (\alpha q)^{q}, 1 \leq j \leq m\right\} \end{aligned}

Prove that the rank of $\mathcal{A}_{x}$ is $m$ .

(d)

Use (c) above to prove Lemma 7.14.

Example 7.13 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 7.1 "NP"

IP is in $\mathrm{NP}$ .

References

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.