  Partitioning a connected graph into $k$~vertex-disjoint connected subgraphs
of similar (or given) orders is a classical problem that has been intensively
investigated since late seventies. Given a connected graph $G=(V,E)$ and a
weight function $w : V \to \mathbb{Q}_\geq$, a connected $k$-partition of $G$
is a partition of $V$ such that each class induces a connected subgraph. The
balanced connected $k$-partition problem consists in finding a connected
$k$-partition in which every class has roughly the same weight. To model this
concept of balance, one may seek connected $k$-partitions that either maximize
the weight of a lightest class $(\text{max-min BCP}_k)$ or minimize the weight
of a heaviest class $(\text{min-max BCP}_k)$. Such problems are equivalent when
$k=2$, but they are different when $k\geq 3$. In this work, we propose a simple
pseudo-polynomial $\frac{k}{2}$-approximation algorithm for $\text{min-max
BCP}_k$ which runs in time $\mathcal{O}(W|V||E|)$, where $W = \sum_{v \in V}
w(v)$. Based on this algorithm and using a scaling technique, we design a
(polynomial) $(\frac{k}{2} +\varepsilon)$-approximation for the same problem
with running-time $\mathcal{O}(|V|^3|E|/\varepsilon)$, for any fixed
$\varepsilon>0$. Additionally, we propose a fixed-parameter tractable algorithm
based on integer linear programming for the unweighted $\text{max-min BCP}_k$
parameterized by the size of a vertex cover.
