ISE seminar 2-22-11

SPRING 2011 SEMINAR SERIES
 
TITLE:                     Polytopes and Arrangements: Diameter and Curvature
 
SPEAKER:               Dr. Yuriy Zinchenko, Assistant Professor of Mathematics 
                                University of Calgary, Canada
 
DATE / TIME:         Tuesday, February 22, 2011
                                1:30 – 2:30 p.m.
 
LOCATION:             Room 375 Mohler Lab, 200 W. Packer Avenue 
 
ABSTRACT:  The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as a continuous analogue of its diameter.  Algorithmically, the diameter may be interpreted as an informal guideline for estimating the complexity of solving a particular linear optimization problem with simplex method.  Similarly, the curvature may be thought of as a predictor for the efficiency of path-following interior-point methods on a given problem instance.  We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub.  We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes, which attain the conjectured order of the largest curvature.  We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension d for all polytopes defined by 2d inequalities for all d, then the order of the curvature is less then the number of defining inequalities for all polytopes.
 
BIOGRAPHY:  Dr. Yuriy Zinchenko is an Assistant Professor of Mathematics at the University of Calgary. He received his Ph.D. in Operations Research from Cornell University in 2005. In 2005-2008 Dr. Zinchenko held a post-doctoral position at the Advanced Optimization Laboratory, McMaster University, and in 2006 - 2008 was also a post-doctoral researcher with the Department of Radiation Oncology, Princess Margaret Hospital. In 2007 Dr. Zinchenko was a recipient of 2007 MITACS Award for Best Novel Use of Mathematics in Technology Transfer for his work in optimal and robust radiotherapy design.  Dr. Zinchenko’s research interests include operations research, optimization algorithms and software, large-scale computational optimization, applications to medicine and health care, particularly, optimal radiation therapy design, scientific parallel computing and high-performance linear algebra.