Title: The Johnson-Lindenstrauss Lemma in Linear and Integer Feasibility
Speaker: Leo Liberti, CNRS LIX, Ecole Polytechnique, France
Slides: The Johnson-Lindenstrauss Lemma for Linear and Integer Feasibility
Date: Wednesday, November 18, 2015 3:00 - 4:00 pm
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbors since they only use Euclidean distances, and it has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this presentation, we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming. This is joint work with Vu Khac Ky and Pierre-Louis Poirion.
Bio:
Leo Liberti obtained a PhD in optimization from Imperial College London in 2004. He became a professor at Ecole Polytechnique in 2006, and worked at IBM Research in 2012-2015 before joining CNRS and becoming a Research Director. His main interests are Mixed-Integer Nonlinear Programming and Distance Geometry.