Tropicalizing the simplex algorithm

Xavier Allamigeon; Pascal Benchimol; Stéphane Gaubert; Michael Joswig

doi:10.1137/130936464

Tropicalizing the simplex algorithm

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig

TU Berlin

Research output: Contribution to journal › Article › peer-review

Abstract

We develop a tropical analogue of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m + n)) time, where m is the number of constraints and n is the dimension.

Original language	English
Pages (from-to)	751-795
Number of pages	45
Journal	SIAM Journal on Discrete Mathematics
Volume	29
Issue number	2
DOIs	https://doi.org/10.1137/130936464
Publication status	Published - 1 Jan 2015

Keywords

Linear programming
Simplex method
Tropical geometry

Access to Document

10.1137/130936464

Cite this

@article{9cecd6518fc6447fb4d9cb670a109f02,

title = "Tropicalizing the simplex algorithm",

abstract = "We develop a tropical analogue of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m + n)) time, where m is the number of constraints and n is the dimension.",

keywords = "Linear programming, Simplex method, Tropical geometry",

author = "Xavier Allamigeon and Pascal Benchimol and St{\'e}phane Gaubert and Michael Joswig",

note = "Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2015",

month = jan,

day = "1",

doi = "10.1137/130936464",

language = "English",

volume = "29",

pages = "751--795",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

number = "2",

}

TY - JOUR

T1 - Tropicalizing the simplex algorithm

AU - Allamigeon, Xavier

AU - Benchimol, Pascal

AU - Gaubert, Stéphane

AU - Joswig, Michael

PY - 2015/1/1

Y1 - 2015/1/1

N2 - We develop a tropical analogue of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m + n)) time, where m is the number of constraints and n is the dimension.

AB - We develop a tropical analogue of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m + n)) time, where m is the number of constraints and n is the dimension.

KW - Linear programming

KW - Simplex method

KW - Tropical geometry

U2 - 10.1137/130936464

DO - 10.1137/130936464

M3 - Article

AN - SCOPUS:84938054063

SN - 0895-4801

VL - 29

SP - 751

EP - 795

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Tropicalizing the simplex algorithm

Abstract

Keywords

Access to Document

Fingerprint

Cite this