next up previous contents index
Next: Open Questions Up: Applications/New Directions Previous: Order vs. Analysis

Distance Problems

Another formulation of the fixed point property is to say that for every order-preserving map there is a p that has distance 0 from its image. As this article is about algorithmic approaches (toward which the author is strongly biased), we did not touch upon this. However M. Roddy's proof of the product conjecture in [104] and the work in [82] use this approach, showing the strength of this point of view. It would be interesting to see how much further this approach can be taken. For example with respect to Xia's algorithm it is easy to see that Xia's algorithm removes all edges tex2html_wrap_inline12412 with d(a,c)<d(b,d) from the (fixed point free) endomorphism graph. It also removes all edges tex2html_wrap_inline12416 for which there is an tex2html_wrap_inline12418 that is comparable to all elements of H from the fixed point free endomorphism graph. What other removals can be guaranteed via similar arguments? As a consequence, how much of a performance gain over the depth-first search can be guaranteed?