Bonchi, F;
Di Giorgio, A;
Zanasi, F;
(2021)
From Farkas’ lemma to linear programming: An exercise in diagrammatic algebra.
In:
Proceedings of the 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021).
(pp. 9.1-9.19).
Schloss Dagstuhl - Leibniz-Zentrum: Dagstuhl, Germany.
Preview |
Text
LIPIcs-CALCO-2021-9.pdf - Published Version Download (924kB) | Preview |
Abstract
Farkas’ lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas’ lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved.
| Type: | Proceedings paper |
|---|---|
| Title: | From Farkas’ lemma to linear programming: An exercise in diagrammatic algebra |
| Event: | 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021) |
| ISBN-13: | 9783959772129 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.CALCO.2021.9 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.CALCO.2021.9 |
| Language: | English |
| Additional information: | © Filippo Bonchi, Alessandro Di Giorgio, and Fabio Zanasi; licensed under Creative Commons License CC-BY 4.0 |
| Keywords: | String diagrams, Farkas Lemma, Duality, Linear Programming |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10140512 |
Archive Staff Only
 |
View Item |
