I am doing a project on task assignment with geographic constraints which naturally leads to the following question. Let $\mathbb{N}$ denote the set of integers. Given a finite subset $A \subset \mathbb{N}$ and a function $T: A \rightarrow \mathbb{N}$, let $R(T)$ denote the range of $T$ and define $${\rm cost}_r(T)= \sum_{i,j \in R(T)} { 1}_{\{|i-j| \leq r\}}.$$ Here $r$ is some nonnegative integer. In  words, we ``pay'' for any two points in the range of $T$ that are sufficiently close.   The problem I would like to solve is the following. Given:a set $A \subset \mathbb{N}$nonnegative integers $d,r,c$does there exist a map $T: A \rightarrow N$ such that$|T(a)-a| \leq d$ for all $a \in A$.${\rm cost}_r(T) \leq c$.In words, can we achieve a very spread out range for $T$ (captured in the constraint that the cost is at most $c$) while simultaneously mapping every element close to itself (captured in the constraint that $|T(a)-a| \leq d$)? My most basic question is whether this problem is polynomial time or NP-hard. Informally it feels like this question is optimizing something nonconvex over matchings, which suggests it should be NP-hard; but the underlying ``graph'' is a simple one which only allows nodes to be matched to other nodes not to far away, and maybe there is a way to use this restrictive structure to get a polynomial time algorithm. I call these ``matching-like'' in the title since if $c=0$ and $r=0$, the map $T$ has to be one-to-one, meaning it defines a matching.If any one has any pointers to similar problems considered in the literature, that would be most helpful.
Looking for a matching-like mapping with a spread constraint
algorithms;np complete;matching