The department hosts a Research Seminar Series, which is open to undergraduate and graduate students; we strongly encourage you to attend the seminars because they are very helpful to identify research interests, and are a chance to meet faculty and other students.
Stay connected with the department, visit the following links: Calendar, Student Organizations, and Scholarships, Awards, and Opportunities to locate opportunities available to you as UTEP CS students.
Chubanov’s method – a new polynomial-time algorithm for linear programming
11:00am-12:00pm, September 7, room CCSB 1.0702
Presented by Professor Kreinovich
In many practical situations, we need to optimize a linear function under linear constraints (equalities or inequalities); such problems are known as problems of linear programming. Since the optimum is always attained at one of the vertices of the corresponding polyhedral domain, the original algorithm for solving linear programming problems – called simplex method – moves along these vertices. While this method has reasonable average computation time, its worst-case complexity is exponential. The first polynomial-time algorithm for linear programming problems was proposed in 1979, its main idea was to enclose the domain by an ellipsoid, to bisect it, to select the half that contains the optimum, to enclose this half in an ellipsoid, and to continue with this new ellipsoid.
Recently, a new polynomial-time algorithm for linear programming was proposed by Sergey Chubanov. It is a modification of the known iterative relaxation algorithm, in which we repeatedly cycle through all the constraints and on each step, among all the points satisfying a currently selected constraint, find the point closest to the current one. For linear programming, this idea works but leads to slow (worst-case exponential-time) convergence. Chubanov showed that we can speed it up to polynomial time if – similarly to resolution method in logic — in addition to the originally given constraints, we also generate new derivative constraints and use them in the iterations.
This innovative idea of generating new constraints has already led to several new efficient algorithms in constraint optimization in general.