We present a general discussion of what constitutes a market‐oriented approach to optimization. We demonstrate how a general framework can be used to conceptually improve two well‐known approaches from the literature, and discuss computational properties of the different approaches. We also show how existing theory could be adjusted to be directly applicable to the theory of the two approaches, thus proving special theory unnecessary. We want to bring out the pedagogical aspects of market mechanisms, to take full advantage of its potential.

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O (√log n /log log n ) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y . This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O (log n /log log n ) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n , the word length W , and the maximal key U < 2 W : O (min log log n + log n /log W , log log n ⋅ log log U /log log log U ). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n .

We introduce a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. Based on this we present optimal bounds for ...

Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$ characters in the worst case.

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range O. .2W -1 in O (n log log n) time, for arbitrary w z log n, a significant improvement over the bound of O (n-) achieved by the fusion trees of Fredman and Willard.Provided that w 2 (log n)z+', for some fixed e > 0, the sorting can even be accomplished in linear expected time with a randomized algorithm.Both of our algorithms parallelize without loss on a unitcost PRAM with a word length of w bits.The first one yields an algorithm that uses O (log n) time and O (n log log n) operations on a deterministic CRCW PRAM.The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w 2 (log n)2+' for some fixed c >0.Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

We present a significant improvement on linear space deterministic sorting and searching. On a unit-cost RAM with word size w, an ordered set of n w-bit keys (viewed as binary strings or integers) can be maintained in O(min{[/spl radic/(logn)][logn/logw+loglogn][logwloglogn]}) time per operation, including insert, delete, member search, and neighbour search. The cost for searching is worst-case while the cost for updates is amortized. As an application, n keys can be sorted in linear at O(n/spl radic/(logn)) worst-case cost. The best previous method for deterministic sorting and searching in linear space has been the fusion trees which supports updates and queries in O(logn/loglogn) amortized time and sorting in O(nlogn/loglogn) worst-case time. We also make two minor observations on adapting our data structure to the input distribution and on the complexity of perfect hashing.

In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984).

We show that a unit-cost RAM with word length w can maintain an ordered set of w-bit integers (or binary strings) under the operations search, insert, delete, nearest neighbour in O(/spl radic/(logn)) worst-case time and range queries in O(/spl radic/(logn)+size of output) worst-case time. The operations rely on AC/sup 0/ instructions only, thereby solving an open problem posed by Fredman and Willard. The data structure is simple. We also present a static data structure that can process a set of /spl Theta/O(logn) searches in O(lognloglogn) time.

We show that given a k-character query string and an ai-ray of n strings arranged in alphabetical order, finding a matching string or report that no such string exists requires a ( k log log n +k+logn log log (4+ k 1;:;; n ) )character comparisons in the worst case, which is tight.

We present a solution to the dictionary problem, where each subset of size n of an ordered universe is represented by a unique structure containing a (unique) binary search tree. The structure permits the execution of search, insert, and delete operations in $O(n^{1/3})$ time in the worst case. We also give a general lower bound, stating that for any unique representation of a set in a graph of bounded out-degree, one of the operations search or update must require a cost of $\Omega(n^{1/3})$. Therefore, our result sheds new light on previously claimed lower bounds for the unique representation of dictionaries.

Abstract We study the problem of string searching using the traditional approach of storing all unique substrings of the text in a suffix tree. The methods of path compression, level compression and data compression are combined to build a simple, compact and efficient implementation of a suffix tree. Based on a comparative discussion and extensive experiments, we argue that our new data structure is superior to previous methods in many practical situations.

We present new improved algorithms for the sorting problem. The algorithms are not only efficient but also clear and simple. First, we introduce Forward Radix Sort which combines the advantages of traditional left-to-right and right-to-left radix sort in a simple manner. We argue that this algorithm will work very well in practice. Adding a preprocessing step, we obtain an algorithm with attractive theoretical properties. For example, n binary strings can be sorted in /spl Theta/ (n log(B/(n log n)+2)) time, where B is the minimum number of bits that have to be inspected to distinguish the strings. This is an improvement over the previously best known result by Paige and Tarjan (1987). The complexity may also be expressed in terms of H, the entropy of the input: n strings from a stationary ergodic process can be sorted in /spl Theta/ (n log(1/H+1)) time an improvement over the result recently presented by Chen and Reif (1993).>

Article Free Access Share on The complexity of searching a sorted array of strings Authors: Arne Andersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, SwedenView Profile , Torben Hagerup Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, GermanyView Profile , Johan Håstad Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, Sweden Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, SwedenView Profile , Ola Petersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, SwedenView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 317–325https://doi.org/10.1145/195058.195175Published:23 May 1994Publication History 6citation285DownloadsMetricsTotal Citations6Total Downloads285Last 12 Months16Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors present a solution to the dictionary problem where each subset of size n of an ordered universe is represented by a unique structure, containing a (unique) binary search tree. The structure permits the execution of search, insert, and delete operations in O(n/sup 1/3/) time in the worst case. They also give a general lower bound, stating that for any unique representation of a set in a graph of, bounded outdegree, one of the operations search or update must require a cost of Omega (n/sup 1/3/) Therefore, the result sheds new light on previously claimed lower bounds for unique binary search tree representations.>

Abstract An algorithm for searching in a binary search tree using two‐way comparisons is presented. The number of comparisons required by this algorithm is only one more than when using three‐way comparisons. Since most high‐level programming languages do not supply three‐way comparisons, the number of comparisons used de facto is reduced by a factor of two. We give experimental results to indicate the speed‐up that may be achieved by the presented algorithm.

Brinck and Foo1,2 have analysed tree traversal algorithms using threads and stack. In this note we show that, contrary to the results in the two referred papers, a preorder traversal is performed faster with a stack than with threads, in terms of pointer assignments. Moreover, the preorder-stack traversal is faster than any of the other standard traversals analysed in Refs 1 and 2.