  We consider the allocation of indivisible objects among agents with different
valuations, which can be positive or negative. An egalitarian allocation is an
allocation that maximizes the smallest value given to an agent; finding such an
allocation is NP-hard. We present a simple polynomial-time algorithm that finds
an allocation that is Pareto-efficient and almost-egalitarian: each agent's
value is at least his value in an egalitarian allocation, minus the absolute
value of a single object. The main tool is an algorithm for rounding a
fractional allocation to a discrete allocation, by which each agent loses at
most one good or gains at most one chore. Our algorithm generalizes and
simplifies three previous algorithms. We discuss several aspects and
observations about the algorithm and the problem at hand that open doors for
efficient and robust implementations.
