  We study the problem of fair and efficient allocation of a set of indivisible
goods to agents with additive valuations using the popular fairness notions of
envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in
conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time
algorithm to compute an EF1+PO allocation and a non-constructive proof of the
existence of allocations that are both EF1 and fractionally Pareto-optimal
(fPO), which is a stronger notion than PO. We present a pseudo-polynomial time
algorithm to compute an EF1+fPO allocation, thereby improving the earlier
results. Our techniques also enable us to show that an EQ1+fPO allocation
always exists when the values are positive and that it can be computed in
pseudo-polynomial time.
  We also consider the class of $k$-ary instances where $k$ is a constant,
i.e., each agent has at most $k$ different values for the goods. For such
instances, we show that an EF1+fPO allocation can be computed in strongly
polynomial time. When all values are positive, we show that an EQ1+fPO
allocation for such instances can be computed in strongly polynomial time.
Next, we consider instances where the number of agents is constant and show
that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial
time. These results significantly extend the polynomial-time computability
beyond the known cases of binary or identical valuations.
  We also design a polynomial-time algorithm that computes a Nash welfare
maximizing allocation when there are constantly many agents with constant many
different values for the goods. Finally, on the complexity side, we show that
the problem of computing an EF1+fPO allocation lies in the complexity class
PLS.
