New algorithms for linear optimization in infinite-dimensional spaces

• Applicant: Privatdozent Dr. Sergei Chubanov
• Subject Area: Mathematics
• Term: from 2018 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 397018931

Linear problems in infinite-dimensional spaces are a much more flexible modeling tool than usual finite-dimensional linear problems. The payment for this is that these problems are much more difficult than finite-dimensional linear problems. For instance, the minimum-cost flow over time problem, which is in fact a linear problem in a Hilbert space, is NP-hard. The main objective of this project is to develop efficient algorithms for a wide spectrum of infinite-dimensional linear problems including such important problem classes as flow over time problems and continuous linear programs. The new algorithms will have guaranteed performance characteristics in terms of a model of computation consisting of operations specific to Hilbert spaces. In the case of finite-dimensional spaces, any algorithm with such characteristics must be at the same time a polynomial algorithm for linear programming. On the other hand, in the infinite-dimensional case, the new algorithms will work in the original space of the problem, in contrast to many traditional discretization methods.

• DFG Programme: Research Grants