Powered by OpenAIRE graph
Found an issue? Give us feedback

New strongly polynomial algorithms for network optimisation problems

Funder: UK Research and InnovationProject code: EP/M02797X/1
Funded under: EPSRC Funder Contribution: 96,770 GBP
visibility
download
views
OpenAIRE UsageCountsViews provided by UsageCounts
downloads
OpenAIRE UsageCountsDownloads provided by UsageCounts
17
78

New strongly polynomial algorithms for network optimisation problems

Description

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.

Data Management Plans
  • OpenAIRE UsageCounts
    Usage byUsageCounts
    visibility views 17
    download downloads 78
  • 17
    views
    78
    downloads
    Powered byOpenAIRE UsageCounts
Powered by OpenAIRE graph
Found an issue? Give us feedback

Do the share buttons not appear? Please make sure, any blocking addon is disabled, and then reload the page.

All Research products
arrow_drop_down
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=ukri________::fa1e61e899e1109d5dff28c093f3d838&type=result"></script>');
-->
</script>
For further information contact us at helpdesk@openaire.eu

No option selected
arrow_drop_down