We consider two variants of the classical bin packing problem in
which items may be {\em fragmented}. This can potentially reduce
the total number of bins needed for packing the instance. However,
since fragmentation incurs overhead, we attempt to avoid it as
much as possible. In {\em bin packing with size increasing
fragmentation (BP-SIF)}, fragmenting an item increases the input
size (due to a header/footer of fixed size that is added to each
fragment). In {\em bin packing with size preserving fragmentation
(BP-SPF)}, there is a bound on the total number of fragmented
items. These two variants of bin packing capture many practical
scenarios, including message transmission in community TV
networks, VLSI circuit design and preemptive scheduling on
parallel machines with setup times/setup costs.

While both BP-SPF and BP-SIF do not belong to the class of
problems that admit a {\em polynomial time approximation scheme
(PTAS)}, we show in this paper that both problems admit a {\em
dual} PTAS and an {\em asymptotic} PTAS. We also develop for each
of the problems a dual asymptotic {\em fully polynomial time
approximation scheme (AFPTAS)}. The AFPTASs are based on a
non-trivial application of a fast combinatorial FPTAS for packing
linear programs with negative entries, proposed recently by Garg
and Khandekar~\cite{gk-04}.