We prove new iterative algorithms to provide component-wise bounds of the steady-state distribution of an irreducible and aperiodic Markov chain. These bounds are based on simple properties of (max,+) and (min,+) sequences. The bounds are improved at each iteration. Thus, we have a clear trade-off between tightness of the bounds (some algorithms converge to the true solution) and computation times. Copyright © 2011 John Wiley & Sons, Ltd.