New strongly polynomial algorithms for network optimisation problems

这项研究对组合优化的基本主题做出了贡献，旨在为新的线性和非线性优化问题设计强多项式算法。多项式时间复杂性的概念于20世纪70年代引入，是衡量各种算法计算效率的标准方法。强多项式时间算法自然地强化了这一概念：算术运算的数量不应取决于问题描述中的成本或容量等数值参数，而应仅取决于此类参数的数量。强多项式算法是许多重要的优化问题的已知算法。然而，对于一个非常基本的优化问题：线性规划，设计这样一个算法仍然是一个悬而未决的问题，其最重要的目标是为每列最多有两个非零条目的线性规划开发一个强多项式算法。这个问题等同于网络流理论中的经典模型--最小成本广义流。即使对于流量最大化的特殊情况，寻找强多项式算法也是一个长期悬而未决的问题，申请人在最近的一篇论文中解决了这一问题。该建议的进一步目标包括相关非线性优化问题的强多项式算法。非线性凸网流模型在数理经济学的市场均衡计算中有着重要的应用。很少有已知的非线性问题允许强多项式算法。该提案旨在对这些问题进行系统研究，并将有助于理解市场均衡模型的计算方面。

The proposed research contributes to fundamental topics in Combinatorial Optimisation, aiming to devise strongly polynomial algorithms for new classes of linear and nonlinear optimisation problems.The notion of polynomial-time complexity, introduced in the 1970s, is a standard way to capture computational efficiency of a wide variety of algorithms. Strongly polynomial-time algorithms give a natural strengthening of this notion: the number of arithmetic operations should not depend on numerical parameters such as costs or capacities in the problem description, but only on the number of such parameters. Strongly polynomial algorithms are known for many important optimisation problems. However, it remains an outstanding open problem to devise such an algorithm for a very fundamental optimisation problem: Linear Programming.The most important goal of the proposal is to develop a strongly polynomial algorithm for linear programs with at most two nonzero entries per column. The problem is equivalent to minimum-cost generalised flows, a classical model in the theory of network flows. Finding a strongly polynomial algorithm was a longstanding open question even for the special case of flow maximisation, resolved by the applicant in a recent paper.Further goals of the proposal include strongly polynomial algorithms for related nonlinear optimisation problems. Nonlinear convex network flow models have important applications for market equilibrium computation in mathematical economics. Very few nonlinear problems are known to admit strongly polynomial algorithms. The proposal aims for a systematic study of such problems, and will also contribute to the understanding of computational aspects of market equilibrium models.