# Welcome to MWiki

## Theorem of the month

The centre method solves every solvable LP in $\displaystyle{ \mathcal{O}(\omega{\vartheta}^{2}) }$.

## Proof and algorithm

Let $\displaystyle{ z := \grave{m} + n }$ and $\displaystyle{ d \in [0, 1] }$ the density of $\displaystyle{ A }$. First, normalise and scale $\displaystyle{ {b}^{T}y - {c}^{T}x \le 0, Ax \le b }$ as well as $\displaystyle{ {A}^{T}y \ge c }$. Let $\displaystyle{ P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y - {c}^{T}x \le r \in [0, \check{r}], Ax - b \le \underline{r}_m, c - {A}^{T}y \le \underline{r}_n\} }$ have the radius $\displaystyle{ \check{r} := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}| }$ and the scaling factor $\displaystyle{ s \in [1, 2] }$. It follows $\displaystyle{ \underline{0}_{z} \in \partial P_{\check{r}} }$. By the strong duality theorem, the LP min $\displaystyle{ \{ r \in [0, \check{r}] : (x, y)^T \in P_r\} }$ solves the LPs max $\displaystyle{ \{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\} }$ and min $\displaystyle{ \{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\} }$.

Its solution is the geometric centre $\displaystyle{ g }$ of the polytope $\displaystyle{ P_0 }$. For $\displaystyle{ p_k^* := (\text{min}\,p_k + \text{max}\,p_k)/2 }$ and $\displaystyle{ k = 1, ..., \grave{z} }$ approximate $\displaystyle{ g }$ by $\displaystyle{ p_0 := (x_0, y_0, r_0)^T }$ until $\displaystyle{ ||\Delta p||_1 }$ is sufficiently small. The solution $\displaystyle{ t^o(x^o, y^o, r^o)^T }$ of the two-dimensional LP min $\displaystyle{ \{ r \in [0, \check{r}] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\} }$ approximates $\displaystyle{ g }$ better and achieves $\displaystyle{ r \le \check{r}/\sqrt{\grave{z}} }$. Repeat this for $\displaystyle{ t^o(x^o, y^o)^T }$ until $\displaystyle{ g \in P_0 }$ is computed in $\displaystyle{ \mathcal{O}({}_z\check{r} {}_e\check{r}dmn) }$ if it exists. Numbers of length $\displaystyle{ \mathcal{O}({\omega}) }$ can only be processed in $\displaystyle{ \mathcal{O}(\vartheta) }$ as is generally known.

Solving all two-dimensional LPs $\displaystyle{ \text{min}_k r_k }$ by bisection methods for $\displaystyle{ r_k \in {}^{\omega}\mathbb{R}_{\ge 0} }$ and $\displaystyle{ k = 1, ..., z }$ in $\displaystyle{ \mathcal{O}({\vartheta}^2) }$ each time determines $\displaystyle{ q \in {}^{\omega}\mathbb{R}^k }$ where $\displaystyle{ q_k := \Delta p_k \Delta r_k/r }$ and $\displaystyle{ r := \text{min}_k \Delta r_k }$. Let simplified $\displaystyle{ |\Delta p_1| = … = |\Delta p_{z}| }$. Here min $\displaystyle{ r_z }$ for $\displaystyle{ p^* := p + wq }$ and $\displaystyle{ w \in {}^{\omega}\mathbb{R}_{\ge 0} }$ would be also to solve. If $\displaystyle{ \text{min}_k \Delta r_k r = 0 }$ follows, stop, otherwise repeat until min $\displaystyle{ r = 0 }$ or min $\displaystyle{ r > 0 }$ is sure. If necessary, constraints are temporarily relaxed by the same small modulus.$\displaystyle{ \square }$