  In this paper, we address the approximate minimization problem of Markov
Chains (MCs) from a behavioral metric-based perspective. Specifically, given a
finite MC and a positive integer k, we are looking for an MC with at most k
states having minimal distance to the original. The metric considered in this
work is the bisimilarity distance of Desharnais et al.. For this metric we show
that (1) optimal approximations always exist; (2) the problem has a bilinear
program characterization; and (3) prove that its threshold problem is in PSPACE
and NP-hard. In addition to the bilinear program solution, we present an
approach inspired by expectation maximization techniques for computing
suboptimal solutions to the problem. Experiments suggest that our method gives
a practical approach that outperforms the bilinear program implementation run
on state-of-the-art bilinear solvers.
