  So far, only few bounds on the runtime behavior of Ant Colony Optimization
(ACO) have been reported. To alleviate this situation, we investigate the ACO
variant we call Bivalent ACO (BACO) that uses exactly two pheromone values. We
provide and successfully apply a new Markov chain-based approach to calculate
the expected optimization time, i. e., the expected number of iterations until
the algorithm terminates. This approach allows to derive exact formulae for the
expected optimization time for the problems Sorting and LeadingOnes. It turns
out that the ratio of the two pheromone values significantly governs the
runtime behavior of BACO. To the best of our knowledge, for the first time, we
can present tight bounds for Sorting ($\Theta(n^3)$) with a specifically chosen
objective function and prove the missing lower bound $\Omega(n^2)$ for
LeadingOnes which, thus, is tightly bounded by $\Theta(n^2)$. We show that
despite we have a drastically simplified ant algorithm with respect to the
influence of the pheromones on the solving process, known bounds on the
expected optimization time for the problems OneMax ($O(n\log n)$) and
LeadingOnes ($O(n^2)$) can be re-produced as a by-product of our approach.
Experiments validate our theoretical findings.
