Tropicalizing the Simplex Algorithm
Copyright policy )Tropicalizing the Simplex Algorithm
We develop a tropical analog 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.
v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], linear programming, 004, 510, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], 14T50, 90C05, Tropical geometry, tropical geometry, Optimization and Control (math.OC), Linear programming, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Combinatorics (math.CO), Présentation de l'article arXiv:1308.0454, simplex method, Mathematics - Optimization and Control
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], linear programming, 004, 510, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], 14T50, 90C05, Tropical geometry, tropical geometry, Optimization and Control (math.OC), Linear programming, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Combinatorics (math.CO), Présentation de l'article arXiv:1308.0454, simplex method, Mathematics - Optimization and Control
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).31 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!