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 analyze the one-dimensional bin-packing problem under the assumption that bins have unit capacity, and that items to be packed are drawn from a uniform distribution on [0,1]. Building on some recent work by Frederickson, we give an algorithm which uses n/2+0(n^½) bins on the average to pack n items. (Knodel has achieved a similar result.) The analysis involves the use of a certain 1-dimensional random walk. We then show that even an optimum packing under this distribution uses n/2+0(n^1/2) bins on the average, so our algorithm is asymptotically optimal, up to constant factors on the amount of wasted space. Finally, following Frederickson, we show that two well-known greedy bin-packing algorithms use no more bins than our algorithm; thus their behavior is also in asymptotically optimal in this sense.

A data base is said to allow range restrictions if we may request that only records with some specified field in a specified range be considered when answering a given query. We present a transformation which 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 we are willing to allow increases of a factor of log n in the worst-case time for an operation and in the space used. This is a generalization of a known transformation which works for static structures. We then use this transformation to produce a data structure for range queries in k dimensions with worst-case times of O(log^kn) for each insertion, deletion, or query operation.

(Similar results were achieved independently by Dan Willard. See the remarks at the end of section 1.)

We consider optimization problems on complete graphs with edge weights drawn independently from a fixed distribution. We discuss several methods for analyzing these problems, including greedy methods, applications of Boole's inequality, and exploitation of relationships with results about random unweighted graphs. We illustrate these techniques 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. Next we demonstrate techniques by which we may determine an asymptotic description of the behavior of a greedy algorithm for this problem.

We analyze the expected difference between the solutions to the integer and linear versions of the 0-1 Knapsack Problem. This difference is of interest since it may help understand the efficiency of a fast backtracking algorithm for the integer 0-1 Knapsack Problem. We show that, under a fairly reasonable input distribution, the expected difference is 0(log^2 n/n) and Ω(1/n).

Given a set of points in a k-dimensional space, an orthogonal range query is a request for the number of points in a specified k-dimensional box. We present a dynamic data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries. The worst-case time complexity for n operations is 0(n log^k n); the space used is 0(n log^k-1 n) . (0-notation here is with respect to n; the constant is allowed to depend on k.) This is faster than the best previous algorithm by a factor of log n; the data structure also handles deletions in a more general context than previous fast algorithms.

A graph is an interval graph if and only if each of its vertices can be associated with an interval on the real line in such a way that two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. An efficient algorithm for testing isomorphism of interval graphs is implemented using a data structure called a PQ-tree. The algorithm runs in 0(n + e) steps for graphs having n vertices and e edges. It is shown that for a somewhat larger class of graphs, namely the chordal graphs, isomorphism is as hard as for general graphs.

Given a set of n items with real-valued sizes, the Optimum Partition problem asks how it can be partitioned into two subsets so that the absolute value of the difference of the sums of the sizes over the two subsets is minimized. We present bounds on the probability distribution of this minimum under the assumption that the sizes are independent random variables drawn from a common distribution. For a large class of distributions, we determine the asymptotic behavior of the median of this minimum, and show that it is exponentially small.

We present optimal parallel algorithms to find maximal matchings in two classes of sparse graphs, namely, graphs with bou.nded degree and those which, for some p, are forbidden to have the clique Kp as a minor. This latter class is quite large; for example, planar graphs satisfy this condition, as do graphs with any fixed bound on their genus. Our algorithms use O(log n) time on a CRCW PRAM for both classes of graphs. On an EREW PRAM, our algorithms use O(log n) time for graphs with bounded degree and O(log n log* n) time for graphs with forbidden Kp-minors.