Details of Grant 

EPSRC Reference:	EP/M02797X/1
Title:	New strongly polynomial algorithms for network optimisation problems
Principal Investigator:	Végh, Professor L
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Management Department
Organisation:	London School of Economics & Pol Sci
Scheme:	First Grant - Revised 2009
Starts:	01 June 2015	Ends:	31 May 2017	Value (£):	96,770
EPSRC Research Topic Classifications:	Fundamentals of Computing Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 03 Mar 2015 EPSRC Mathematics Prioritisation Panel March 2015 Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.lse.ac.uk