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.