2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Intriguing question. Conjecture: without loss of generality we can assume $T$ is monotone increasing. Or, in other words, I'd conjecture there exists an optimal solution $T$ such that $T(a)<T(b)$ for all $a,b \in A$ with $a<b$. Does this seem true? Can it be proven (e.g., by a local swapping argument)? If so, I think there is a dynamic programming algorithm whose running time is polynomial in $|A|,d,c$ and exponential in $r$, if that helps. $\endgroup$ – D.W. Dec 23 '16 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.