Feasible gradients in Gravitational Method for Linear Programming

The Gravitational Method for Linear Programming (LP) promises to be a serious practical algernative to Simplex method. The authors prove a nontrivial property of the Gravitational method by showing that the magnitude of the feasible gradient improves monotonically as the algorithm progress. As a corollary they obtain a simple proof of finite convergence of the algorithm, which does not employ the bit complexity factor L. The crucial component in an efficient implementation of the Gravitational method is the computation of the feasible gradient at a vertex. The authors outline an algorithm (for computing the feasible gradient at a vertex) that employs interior-point computation and is expected to be efficient practically. Computational behaviour of the proposed scheme is being studied.