  This paper introduces the Simultaneous assignment problem. Let us given a
graph with a weight and a capacity function on its edges, and a set of its
subgraphs along with a degree upper bound function for each of them. We are
also given a laminar system on the node set with an upper bound on the
degree-sum in each member of the system. Our goal is to assign each edge a
non-negative integer below its capacity such that the total weight is
maximized, the degrees in each subgraph are below the associated degree upper
bound, and the degree-sum bound is respected in each member of the laminar
system.
  We identify special cases when the problem is solvable in polynomial time.
One of these cases is a common generalization of the hierarchical $b$-matching
problem and the laminar matchoid problem. This implies that both problems can
be solved efficiently in the weighted, capacitated case even if both lower and
upper bounds are present -- generalizing the previous polynomial-time
algorithms. The problem is solvable for trees provided that the laminar system
is empty and a natural assumption holds for the subgraphs.
  The general problem, however, is shown to be APX-hard in the unweighted case,
which implies that the $d$-distance matching problem is APX-hard. Furthermore,
we prove that the approximation guarantee of any polynomial-time algorithm must
increase linearly in the number of the given subgraphs unless P=NP. We give a
generic framework for deriving approximation algorithms, which can be applied
to a wide range of problems. As an application to our problem, a
constant-approximation algorithm is derived when the number of the subgraphs is
a constant. The approximation guarantee is the same as the integrality gap of a
strengthened LP-relaxation when the number of the subgraphs is small. Improved
approximation algorithms are given when the degree bounds are uniform or the
graph is sparse.
