3
$\begingroup$

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be $K$-biLipchitz so that $\phi^2 = \phi\circ\phi$ is within $\epsilon$ of the identity. That is,

$$\frac{1}{K} d(m,n) \leq d(\phi(m),\phi(n)) \leq K d(m,n), \text{ and }$$ $$ d(\phi^2(m),m) \leq \epsilon$$

where the first line holds across all pairs $(m,n)$ in $M$ and the second line for all $m$ in $M$. Here are my questions:

Is there a polynomial time (in the number of points of $M$) algorithm to check for the existence of such a $\phi$? And if so, what is it? Otherwise, are there "reasonably effective" techniques to approximate this problem?

I've tried reducing this to the Hall theorem and to linear programming but to no avail so far. It would be great if the algorithm actually produced one or more such $\phi$'s, but for now I'd just be happy with something that outperforms my idiotic brute-force approach and furnishes a yes/no answer for existence.

Improve this question
$\endgroup$
2
  • $\begingroup$ Also, are we assuming that $\epsilon\ge \min d$, so that $\phi^2\not= \textrm{id}$ remains a possibility? $\endgroup$
    – Christian Remling
    Jul 7, 2014 at 23:56
  • $\begingroup$ @ChristianRemling yes. $\endgroup$
    – Vidit Nanda
    Jul 8, 2014 at 1:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.