Friday, 11:30 - 11:55 h, Room: H 0112


Jianming Shi
A computational geometric approach for solving linear programming: Toward strong polynomial

Coauthor: Shi Jianming


The complexity of linear programming (LP) is still open because we don't know whether there exists a strongly polynomial algorithm for solving a Linear program. This talk is an effort toward this long-standing open problem.
Unlike previous approaches, the algorithm proposed in talk does not require the information of the vertices of the feasible region. Under the assumption that an interior point in the feasible region is available, we reformulate a LP as a computational geometric problem with a convex hull of the data points (vectors).
We will report the experiments results comparing the new approach and the existing methods, like the interior point method, Simplex method.


Talk 3 of the contributed session Fri.1.H 0112
"Complexity issues in optimization" [...]
Cluster 16
"Nonlinear programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. They were lucky to produce Viagra Sublingual which dissolves under the tongue and penetrates into the blood causing erection faster than any other drugs.