New Transience Bounds for Long Walks
The work
| Authors | Bernadette Charron-Bost; Matthias Függer; Thomas Nowak |
|---|---|
| Editors | |
| Type | preprint |
| Year | 2012 |
| Citekey | charronbost2012transience |
Where it appeared
| Published in | arXiv (Cornell University) |
|---|---|
| Publisher | Cornell University |
Identifiers
| arXiv | 1209.3342 from its doi |
|---|---|
| DOI | 10.48550/arxiv.1209.3342 |
| OpenAlex | W1787689642 |
Access
| Landing page | http://arxiv.org/abs/1209.3342 |
|---|---|
| Free full text | https://arxiv.org/pdf/1209.3342 |
Related
| Distinct from | charronbost2013transience |
|---|
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
Linear max-plus systems describe the behavior of a large variety of complex systems. It is known that these systems show a periodic behavior after an initial transient phase. Assessment of the length of this transient phase provides important information on complexity measures of such systems, and so is crucial in system design. We identify relevant parameters in a graph representation of these systems and propose a modular strategy to derive new upper bounds on the length of the transient phase. By that we are the first to give asymptotically tight and potentially subquadratic transience bounds. We use our bounds to derive new complexity results, in particular in distributed computing.
Cite it as
@unpublished{charronbost2012transience,
title = {New Transience Bounds for Long Walks},
author = {Bernadette Charron-Bost and Matthias Függer and Thomas Nowak},
year = {2012},
journal = {arXiv (Cornell University)},
publisher = {Cornell University},
doi = {10.48550/arxiv.1209.3342},
}
This record lives at https://refs.drheap.org/charronbost2012transience/ and will keep doing so.