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.

## Type of Work

Article (1433) Book (0) Theses (0) Multimedia (0)

## Peer Review

Peer-reviewed only (1430)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (1354) UC Davis (201) UC Irvine (1368) UCLA (204) UC Merced (5) UC Riverside (36) UC San Diego (12) UCSF (58) UC Santa Barbara (6) UC Santa Cruz (1305) UC Office of the President (38) Lawrence Berkeley National Laboratory (1370) UC Agriculture & Natural Resources (0)

## Department

Physics Department (1295) Physical Sciences (1210) Computing Sciences (1147) Department of Animal Science (157) Berkeley Law (144) UCLA School of Education and Information Studies (118)

## Journal

Proceedings of the Annual Meeting of the Cognitive Science Society (5) Ufahamu: A Journal of African Studies (1)

## Discipline

Physical Sciences and Mathematics (12) Engineering (4) Social and Behavioral Sciences (4)

## Reuse License

BY - Attribution required (909) BY-NC - Attribution; NonCommercial use only (48)

## Scholarly Works (1434 results)

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.