  In this paper, we study how to fairly allocate a set of m indivisible chores
to a group of n agents, each of which has a general additive cost function on
the items. Since envy-free (EF) allocations are not guaranteed to exist, we
consider the notion of envy-freeness up to any item (EFX). In contrast to the
fruitful results regarding the (approximation of) EFX allocations for goods,
very little is known for the allocation of chores. Prior to our work, for the
allocation of chores, it is known that EFX allocations always exist for two
agents or general number of agents with identical ordering cost functions. For
general instances, no non-trivial approximation result regarding EFX allocation
is known. In this paper, we make progress in this direction by providing
several polynomial time algorithms for the computation of EFX and approximately
EFX allocations. We show that for three agents we can always compute a
4.45-approximation of EFX allocation. For n>=4 agents, our algorithm always
computes a (3n^2-n)-approximation. We also study the bi-valued instances, in
which agents have at most two cost values on the chores. For three agents, we
provide an algorithm for the computation of EFX allocations. For n>=4 agents,
we present algorithms for the computation of partial EFX allocations with at
most n-1 unallocated items; and (n-1)-approximation of EFX allocations.
