Skip to main content
MathOverflow

Return to Question

added 13 characters in body
Source Link
Vidit Nanda
Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125

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.

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 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.

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.

Source Link
Vidit Nanda
Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125

Algorithm to construct metric space endomorphism with controlled square

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 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.