  We consider the well-studied Hospital Residents (HR) problem in the presence
of lower quotas (LQ). The input instance consists of a bipartite graph $G =
(\mathcal{R} \cup \mathcal{H}, E)$ where $\mathcal{R}$ and $\mathcal{H}$ denote
sets of residents and hospitals respectively. Every vertex has a preference
list that imposes a strict ordering on its neighbors. In addition, each
hospital $h$ has an associated upper-quota $q^+(h)$ and lower-quota $q^-(h)$. A
matching $M$ in $G$ is an assignment of residents to hospitals, and $M$ is said
to be feasible if every resident is assigned to at most one hospital and a
hospital $h$ is assigned at least $q^-(h)$ and at most $q^+(h)$ residents.
  Stability is a de-facto notion of optimality in a model where both sets of
vertices have preferences. A matching is stable if no unassigned pair has an
incentive to deviate from it. It is well-known that an instance of the HRLQ
problem need not admit a feasible stable matching. In this paper, we consider
the notion of popularity for the HRLQ problem. A matching $M$ is popular if no
other matching $M'$ gets more votes than $M$ when vertices vote between $M$ and
$M'$. When there are no lower quotas, there always exists a stable matching and
it is known that every stable matching is popular.
  We show that in an HRLQ instance, although a feasible stable matching need
not exist, there is always a matching that is popular in the set of feasible
matchings. We give an efficient algorithm to compute a maximum cardinality
matching that is popular amongst all the feasible matchings in an HRLQ
instance.
