<b>UNBELIEVABLE</b><b> </b><b><i>O</i></b><b>(</b><b><i>L</i></b>^{<strong>1.5</strong>}<b>)</b><b> </b><b>WORST-CASE</b><b> </b><b>COMPUTATIONAL</b><b> </b><b>COMPLEXITY</b><b>ACHIEVED</b><b> </b><b>BY</b><b> </b><b><i>spdspds</i></b><b> </b

The Symmetric Primal-Dual <i>Sym</i>plex Pivot Decision Strategy (<i>spdspds</i>) is a novel iterative algorithm to solve linear programming problems. A symplex pivoting operation is considered simply as an <i>exchange</i> between a basic (dependent) variable and a non-basic (independent) variable, in the <i>Goldman-Tucker Compact-Symmetric-Tableau</i> (CST) which is a unique symmetric representation common to both the primal as well as the dual of a linear programming problem in its standard canonical form. From this viewpoint, the <i>classical </i><i>simplex</i><i> pivoting</i> operation of Dantzig may be considered as a restricted special case.<br>The <i>infeasibility index</i> associated with a symplex tableau is defined as the sum of the number of primal variables and the number of dual variables that are infeasible. A <i>measure of goodness</i> as a <i>global effectiveness measure</i> of a pivot selection is defined/determined as/by the <i>decrease in the infeasibility index</i> associated with such a pivot selection. The selection of the symplex pivot element is made by seeking the best possible anticipated <i>decrease in the infeasibility index</i> from among a wide range of candidate choices with non-zero values - limited only by considerations of <i>potential numerical instability</i>. After passing through a non-repeating sequence of CST tableaus, the algorithm terminates when further reduction in the infeasibility index is not possible; then the tableau is checked for the <i>terminal tableau type</i> to facilitate the <i>problem classification</i> - a termination with an <i>infeasibility index</i> of <i>zero</i> indicates optimum solution. Even in the absence of an optimum solution, the versatility of the <i>spdspds</i> algorithm allows one to explore/determine the most suitable alternative solutions, including possibly a comprehensive parametric analysis, etc. The worst-case computational complexity of the <i>spdspds</i> algorithm is shown to be <i>O</i>(<i>L</i>^1.5) where L refers to the problem-size expressed in terms of the size(length) of the input data.