Research Initiation Award: Polar Geometric Approach to Linear Programming

点击翻译按钮获取中文摘要

9308953 Prabhu The research will investigate a new approach to Linear Programming (LP). The approach exploits fundamental results from Convex Polytope Theory and Polarity Theory that have not been applied to LP computation previously. Preliminary studies suggest that the approach has prospects of yielding an efficient algorithm that could be faster than the current LP algorithms. The work describes two methods for devising an efficient LP algorithm based on the suggested approach: Gale Transform Method and Simplicial Refinement Method. The methods apply classic results on the combinatorial and metric structure of polytopes to make computation efficient. Computational experiments on the methods will be undertaken in parallel with theoretical investigations in order to ensure that the resulting algorithm will be theoretically efficient. Enormous theoretical and computational research effort has been expended in the past on attempts to convert the edge-following Simplex method into a worst-case polynomial-time algorithm . The Generalized Simple scheme can be significant, in that it proffers a fresh approach to the quest for worst-case polynomial-time Simplex algorithms. If these goals are achieved, the results will have significant impact in solving real world problems.