Paper Info
Title
Idempotent and tropical mathematics; complexity of algorithms and interval analysis.
Abstract
A very brief introduction to tropical and idempotent mathematics is presented. Tropical mathematics can be treated as a result of a dequantization of the traditional mathematics as the Planck constant tends to zero taking imaginary values. In the framework of idempotent mathematics, constructions and algorithms are usually simpler than their traditional analogs. We examine in particular algorithms of tropical/idempotent mathematics generated by a collection of basic semiring (or semifield) operations and other “good” operations. Every algorithm of this type has an interval version. The complexity of this interval version coincides with the complexity of the initial algorithm. The interval version of an algorithm of this type gives exact interval estimates for the corresponding output data. Algorithms of linear algebra over idempotent semirings are examined. In this case, basic algorithms, like their interval versions, are polynomial. This situation is very different from the traditional linear algebra case, where basic algorithms are polynomial but the corresponding interval versions are NP-hard and interval estimates are not exact.
Year
DOI
Venue
2013
10.1016/j.camwa.2012.09.008
Computers & Mathematics with Applications
Keywords
DocType
Volume
Tropical mathematics,Idempotent mathematics,Complexity of algorithms,Interval analysis
Journal
65
Issue
ISSN
Citations 
10
0898-1221
1
PageRank 
References 
Authors
0.38
5
1
Name
Order
Citations
PageRank
Grigori L. Litvinov1272.75