Title: The Triangle Algorithm: A Robust Geometric Algorithm and Its Applications
Speaker: Bahman Kalantari, Rutgers University
Date: Monday, February 18, 2013 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The recently developed Triangle Algorithm is a fully polynomial-time approximation scheme that tests membership of a distinguished point in the convex hull of a finite set of points in Euclidean space. It is motivated by a geometric duality on convex hulls and a property of a triangle. It has given rise to a new algorithm for linear programming feasibility, a new iterative method for solving linear system of equations, and a new polynomial-time algorithm for bipartite perfect matching. It is surprisingly simple to implement and well-suited for large-scale problems. Preliminary computational results indicate that it could compete with the simplex method in solving LP feasibility, and also with such iterative methods as SOR and AOR. The talk will focus on describing the algorithm, its underlying theory, preliminary computational performance and several applications. There are generalizations of the Triangle Algorithm and non-trivial applications. All these suggest the algorithm could find a wide range of theoretical, algorithmic, and practical applications across different areas.