  Let G = ((A,B),E) be an instance of the stable marriage problem where every
vertex ranks its neighbors in a strict order of preference. A matching M in G
is popular if M does not lose a head-to-head election against any matching.
Popular matchings are a well-studied generalization of stable matchings,
introduced with the goal of enlarging the set of admissible solutions, while
maintaining a certain level of fairness. Every stable matching is a min-size
popular matching. Unfortunately, when there are edge costs, it is NP-hard to
find a popular matching of minimum cost -- even worse, the min-cost popular
matching problem is hard to approximate up to any factor.
  Let opt be the cost of a min-cost popular matching. Our goal is to
efficiently compute a matching of cost at most opt by paying the price of
mildly relaxing popularity. Our main positive results are two bi-criteria
algorithms that find in polynomial time a near-popular or quasi-popular
matching of cost at most opt. Moreover, one of the algorithms finds a
quasi-popular matching of cost at most that of a min-cost popular fractional
matching, which could be much smaller than opt.
  Key to the other algorithm is a polynomial-size extended formulation for an
integral polytope sandwiched between the popular and quasi-popular matching
polytopes. We complement these results by showing that it is NP-hard to find a
quasi-popular matching of minimum cost, and that both the popular and
quasi-popular matching polytopes have near-exponential extension complexity.
  This version of the paper goes beyond the conference version [12] in the
following two points: (i) the algorithm for finding a quasi-popular matching of
cost at most that of a min-cost popular fractional matching is new; (ii) the
proofs from Section 6.1 and Section 7.3 are now self-contained (the conference
version used constructions from [10] to show these lower bounds).
