Journal article
Sparktope: linear programs from algorithms
Abstract
In a recent paper, Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size and its optimum solution contains x as well as a complete execution trace of the algorithm. Their method led us to the construction …
Authors
Avis D; Bremner D
Journal
Optimization Methods and Software, Vol. 37, No. 3, pp. 954–981
Publisher
Taylor & Francis
Publication Date
May 4, 2022
DOI
10.1080/10556788.2020.1864370
ISSN
1055-6788