arrow grid linear view icon
The College of Arts Sciences
Search

You are here

James Renegar

Professor

Frank H T Rhodes Hall, Room 224
renegar@cornell.edu
607-255-9142

Website(s)

Keywords

Optimization algorithms

Research

I am currently devoting the majority of my research efforts to devising new algorithms for linear programming, i.e., for solving systems of linear inequalities. Unlike the situation for linear equations, surprisingly basic problems remain unresolved for linear inequalities. For example, it is unknown whether there exists an algorithm that can solve a general system of linear inequalities using a number of arithmetic operations that is bounded polynomially in the number of variables and the number of inequalities in the system. By contrast, elementary Gaussian elimination (i.e., high-school mathematics) solves a system of n linear equations in n unknowns in roughly n^3 operations.

I am also interested in devising algorithms for more general problems involving hyperbolic polynomials. (A hyperbolic polynomial p is a real multivariate polynomial for which there exists a vector v such that all univariate polynomials obtained by restricting p to lines in the direction v have only real roots.) These polynomials have played an especially important role in optimization in recent years.