Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - February 18, 2013

Linda Casals lindac at dimacs.rutgers.edu
Wed Feb 13 10:32:43 EST 2013


*********************************************************************

DIMACS/CCICADA Interdisciplinary Seminar Series Presents
               
*********************************************************************

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.

DIMACS/CCICADA Interdisciplinary Series Calendar 2013-
See: http://dimacs.rutgers.edu/Seminars/interseminars12-13.html



More information about the Dimacs-ccicada-announce mailing list