  We present a weighted approach to compute a maximum cardinality matching in
an arbitrary bipartite graph. Our main result is a new algorithm that takes as
input a weighted bipartite graph $G(A\cup B,E)$ with edge weights of $0$ or
$1$. Let $w \leq n$ be an upper bound on the weight of any matching in $G$.
Consider the subgraph induced by all the edges of $G$ with a weight $0$.
Suppose every connected component in this subgraph has $\mathcal{O}(r)$
vertices and $\mathcal{O}(mr/n)$ edges. We present an algorithm to compute a
maximum cardinality matching in $G$ in $\tilde{\mathcal{O}}( m(\sqrt{w}+
\sqrt{r}+\frac{wr}{n}))$ time.
  When all the edge weights are $1$ (symmetrically when all weights are $0$),
our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm,
which runs in $\mathcal{O}(m\sqrt{n})$ time. However, if we can carefully
assign weights of $0$ and $1$ on its edges such that both $w$ and $r$ are
sub-linear in $n$ and $wr=\mathcal{O}(n^{\gamma})$ for $\gamma < 3/2$, then we
can compute maximum cardinality matching in $G$ in $o(m\sqrt{n})$ time. Using
our algorithm, we obtain a new $\tilde{\mathcal{O}}(n^{4/3}/\varepsilon^4)$
time algorithm to compute an $\varepsilon$-approximate bottleneck matching of
$A,B\subset\mathbb{R}^2$ and an
$\frac{1}{\varepsilon^{\mathcal{O}(d)}}n^{1+\frac{d-1}{2d-1}}\mathrm{poly}\log
n$ time algorithm for computing $\varepsilon$-approximate bottleneck matching
in $d$-dimensions. All previous algorithms take $\Omega(n^{3/2})$ time. Given
any graph $G(A \cup B,E)$ that has an easily computable balanced vertex
separator for every subgraph $G'(V',E')$ of size $|V'|^{\delta}$, for
$\delta\in [1/2,1)$, we can apply our algorithm to compute a maximum matching
in $\tilde{\mathcal{O}}(mn^{\frac{\delta}{1+\delta}})$ time improving upon the
$\mathcal{O}(m\sqrt{n})$ time taken by the HK-Algorithm.
