It has long been known [Chvátal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length n over an alphabet of size k is asymptotic to γ k n for some constant γ k depending on k . The value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. We discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. To our knowledge, the previous best-known lower and upper bounds for γ 2 were those of Dančík and Paterson, approximately 0.773911 and 0.837623 [Dančík 1994; Dančík and Paterson 1995]. We improve these to 0.788071 and 0.826280. This upper bound is less than the γ 2 given by Steele's old conjecture (see Steele [1997, page 3]) that γ 2 = 2/(1 + √2)≈ 0.828427. (As Steele points out, experimental evidence had already suggested that this conjectured value was too high.) Finally, we show that the upper bound technique described here could be used to produce, for any k , a sequence of upper bounds converging to γ k , though the computation time grows very quickly as better bounds are guaranteed.

The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem. It is assumed that all inequalities are weak. Under the concurrent-read-exclusive-write PRAM model, an $O((\log m + \log^2 n) \log^2 n)$-time parallel algorithm for deciding feasibility is described. It requires $mn^{O(\log n)}$ processors in the worst case, though it is not known whether this bound is tight. When the problem is feasible, a solution can be computed within the same complexity. Moreover, linear programming problems with at most two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors. Consequently, all these problems can be solved sequentially with only $O((\log m + \log ^2 n)^2 \log ^2 n)$ space. (These bounds assume that numbers take $O(1)$ space, and arithmetic on them takes $O(1)$ time; the problem can still be solved in poly-log space as a function of the input size even if a Turing machine model with rational input is used instead.) It is also shown that if the underlying graph has bounded tree-width and an underlying tree is given, then the feasibility problem is in the class NC.

In [GS78] a deep and elegant analysis showed that double hashing was equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we give an analysis which extends this to load factors arbitrarily close to 1. We understand from [Ko86, Gu87] that Ajtai, Guibas, Komlós, and Szemerédi obtained this result in the first part of 1986; the analysis in this paper is of interest nonetheless because we demonstrate how a resampling technique can be used to obtain a remarkably simple proof.

The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed.Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem.We describe an 2 2 O((logm + log n)log n) time parallel algorithm under the concurrent-read-exclusive-write PRAM model for deciding feasibility.It requires mn O(l°gn) processors in the worst case, though we do not know whether this bound is tight.If the coefficients are rational or the set of solutions is bounded then, given the output of the feasibility checking algorithm, a solution can be computed in constant time.Moreover, linear programming problems with two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors.Consequently, all these problems can be solved 2 by sequentially with only 2 2 O((logm + log n) log n) space.It is also shown that if the underlying graph has bounded treewidth and an underlying tree is given then the problem is in the class NC.

A database is said to allow range restrictions if one may request that only records with some specified field in a specified range be considered when answering a given query. A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of O (log n ) in the worst-case time for an operation and in the space used. This is a generalization of a known transformation that works for static structures. This transformation is then used to produce a data structure for range queries in k dimensions with worst-case times of O (log k n ) for each insertion, deletion, or query operation.

We consider the problem of packing n items which are drawn uniformly from intervals of the form [a,b], where 0 ≪ a ≪ b ≪ 1. For a fairly large class of a and b, we determine a lower bound on the asymptotic expected number of bins used in an optimum packing. The method of proof is related to the dual of the linear programming problem corresponding to the bin packing problem. We demonstrate that these bounds are tight by providing simple packing strategies which achieve them.

Optimization problems on complete graphs with edge weights drawn independently, from a fixed distribution, are considered. Several methods for analyzing these problems are discussed, including greedy methods, applications of Boole’s inequality, and exploitation of relationships with results about random unweighted graphs. These techniques are illustrated in the case in which the edge weights are drawn from a normal distribution; in particular, we investigate the expected behavior of the minimum weight clique on k vertices. We describe the asymptotic behavior (in probability and/or almost surely) of the random variable which describes the optimum; we also discuss the asymptotic behavior of its mean. Finally techniques are demonstrated by which we may determine an asymptotic description of the behavior of a greedy algorithm for this problem.

A graph is an interval graph tf and only if each of Its verttces can be associated with an interval on the real hne m such a way that two vertices are adjacent m the graph exactly when the corresponding mtervals have a nonempty mtersectmn An effictent algonthrn for testing tsomorpinsm of interval graphs ts unplemented using a data structure called a PQ-tree.The algorithm runs m O(n + e) steps for graphs having n vemces and e edges It is shown that for a somewhat larger class of graphs, namely the chordal graphs, lsomorpinsm is as hard as for general graphs KEY WORDS AND PHRASES graph tsomorpinsm algonthms, polynomial reduclinhty, intersection graphs, interval graphs, chordal graphs, ngtd clrcmt graphs CR CATEGORIES. 5 25, 5.32 Permission to copy without fee all or part of tins material ,s granted provtded that the

Given a set of points in a d-dimensional space, an orthogonal range query is a request for the number of points in a specified d-dimensional box. We present a data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries. The worstcase time complexity for n operations is O(n logd n); the space usea is O(n logd-1 n). (O-notation here is with respect to n; the constant is allowed to depend on d.) Next we briefly discuss decision tree bounds on the complexity of orthogonal range queries. We show that a decision tree of height O(dn log n) (Where the implied constant does not depend on d or n) can be constructed to process n operations in d dimensions. This suggests that the standard decision tree model will not provide a useful method for investigating the complexity of such problems.

we consider optimization problems on complete graphs with edge weights chosen from identical but independent normal distributions. We show some very general techniques for obtaining upper and lower bounds on the asymptotic behavior of these problems. Often, but not always, these bounds are equal, enabling us to state the asymptotic behavior of the maximum. Problems in which the bounds are tight include finding the optimum traveling salesman tour, finding a minimum cost spanning tree, and finding a heaviest clique on k vertices. We then discuss some greedy heuristic algorithms for these problems.

We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. We give a new linear-time algorithm to calculate the fill-in produced by any elimination ordering, and we give two new related algorithms for finding orderings with special properties. One algorithm, based on breadth-first search, finds a perfect elimination ordering, if any exists, in $O(n + e)$ time, if the problem graph has n vertices and e edges. An extension of this algorithm finds a minimal (but not necessarily minimum) ordering in $O(ne)$ time. We conjecture that the problem of finding a minimum ordering is NP-complete

A matrix of zeroes and ones is said to have the consecutive ones property if there is a permutation of its rows such that the ones in each column appear consecutively. This paper develops a data structure which may be used to test a matrix for the consecutive ones property, and produce the desired permutation of the rows, in linear time. One application of the consecutive ones property is in recognizing interval graphs. A graph is an interval graph if there exists a 1-1 correspondence between its vertices and a set of intervals on the real line such that two vertices are adjacent if and only if the corresponding intervals have a nonempty intersection. Fulkerson and Gross have characterized interval graphs as those for which the clique versus vertex incidence matrix has the consecutive ones property. In testing this particular matrix for the consecutive ones property we may process the columns in a special order to simplify the algorithm. This yields the interval graph recognition algorithm which is presented in section 2; section 3 indicates how this algorithm may be extended to the general consecutive ones problem.