  This paper introduces the \emph{$d$-distance $b$-matching problem}, in which
we are given a bipartite graph $G=(S,T;E)$ with $S=\{s_1,\dots,s_n\}$, a weight
function on the edges, an integer $d\in\mathbb{Z}_+$ and a degree bound
function $b:S\cup T\to\mathbb{Z}_+$. The goal is to find a maximum-weight
subset $M\subseteq E$ of the edges satisfying the following two conditions: 1)
the degree of each node $v\in S\cup T$ is at most $b(v)$ in $M$, 2) if
$s_it,s_jt\in M$, then $|i-j|\geq d$. In the cyclic version of the problem, the
nodes in $S$ are considered to be in cyclic order. We get back the
\emph{(cyclic) $d$-distance matching problem} when $b(s) = 1$ for $s\in S$ and
$b(t) = \infty$ for $t\in T$.
  We prove that the $d$-distance matching problem is APX-hard even in the
unweighted case. We show that $(2-\frac{1}{d})$ is a tight upper bound on the
integrality gap of the natural integer programming model for the cyclic
$d$-distance $b$-matching problem provided that $(2d-1)$ divides the size of
$S$. For the non-cyclic case, the integrality gap is shown to be at most
$(2-\frac{2}{d})$. The proofs give approximation algorithms with guarantees
matching these bounds, and also improve the best known algorithms for the
(cyclic) $d$-distance matching problem. In a related problem, our goal is to
find a permutation of $S$ maximizing the weight of the optimal $d$-distance
$b$-matching. This problem can be solved in polynomial time for the (cyclic)
$d$-distance matching problem -- even though the (cyclic) $d$-distance matching
problem itself is NP-hard and also hard to approximate arbitrarily. For
(cyclic) $d$-distance $b$-matchings, however, we prove that finding the best
permutation is NP-hard even if $b\equiv 2$ or $d=2$, and we give
$e$-approximation algorithms.
