Formalisation of Combinatorial Optimisation in Isabelle/HOL: Network Flows

Add to your list(s) Download to your calendar using vCal

• Thomas Ammer (King's College London)
• Thursday 06 February 2025, 17:00-18:00
• MR14 Centre for Mathematical Sciences.

If you have a question about this talk, please contact Jonas Bayer.

Combinatorial optimisation (CO) is a sub-area of discrete mathematics. Basic examples for CO problems are finding a shortest path or a minimum spanning tree in a graph. So-called network flows or variations of matching would be more advanced problems. There are also abstract concepts like matroids that offer an algebraic point of view and a uniform foundation for some of the more concrete problems.

Since the considered structures are finite, it is a natural aim to compute a solution efficiently. That implies an overlap with the theory of algorithms, especially running time analysis.

This talk is mainly about the Isabelle/HOL formalisation of a specific CO problem, namely, minimum cost flows, which are a subtype of network flows. Among others, this includes Orlin’s Algorithm, which is a most efficient method to compute a minimum cost flow in general networks. Also, the running time argument for this advanced algorithm and some reductions among flow problems were formalised.

=== Hybrid talk ===

Join Zoom Meeting https://cam-ac-uk.zoom.us/j/87143365195?pwd=SELTNkOcfVrIE1IppYCsbooOVqenzI.1

Meeting ID: 871 4336 5195

Passcode: 541180

This talk is part of the Formalisation of mathematics with interactive theorem provers series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS Pure Maths study groups
• DPMMS info aggregator
• DPMMS lists
• Department of Computer Science and Technology talks and seminars
• Formalisation of mathematics with interactive theorem provers
• Hanchen DaDaDash
• Interested Talks
• MR14 Centre for Mathematical Sciences
• School of Physical Sciences
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.