15
$\begingroup$

The order maintenance problem (or "maintaining order in a list") is to support the operations:

  • singleton: creates a list with one item, returns a pointer to it
  • insertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
  • delete: given a pointer to an item, removes it from its list
  • minPointer: given two pointers to items in the same list, returns the one closer to the front of the list

I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.

Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?

$\endgroup$
  • $\begingroup$ Multiplication has only recently (since Pentium III) been in $AC^0$. Can we include solutions which use multiplication? $\endgroup$ – A T Jun 9 '14 at 4:50
  • $\begingroup$ I don't think that's correct. First, I don't think multiplication is in $AC^0$. Second, I don't think particular machines, like the Pentium III you mention, have anything to do with the question of whether multiplication is in $AC^0$. Finally, as demonstrated in the question, I obviously am aware of several multiplication-based algorithms for this problem, so adding more in a new "answer" does not in any way improve things. $\endgroup$ – jbapple Jun 9 '14 at 4:57
  • $\begingroup$ Found where I read about this; it was about Pentium 4 not III; and didn't implement multiplication instead worked around it with a new instruction from that processor: M. Thorup, ‘On AC0 Implementations of Fusion Trees and Atomic Heaps’, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, 2003, pp. 699–707. $\endgroup$ – A T Jun 9 '14 at 9:32
6
$\begingroup$

Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also exercise 8.12 from open data structures and Roura's "A new method for balancing binary search trees".

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.