Browse Prior Art Database

MAXIMIZATION PPM14EM ON GRAPHS WITH EUM WEIGHTS CH0SEN FROM A NORVAL DISTRIBUTION

IP.com Disclosure Number: IPCOM000128326D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

George S. Lueker: AUTHOR [+3]

Abstract

~ie 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 whicn the bounds are tight include finding the optimum traveling salesman tour, finding a minimum cost spanning tree, am finding a heaviest clique on k vertices. We then discuss some greedy heuristic algorithms for these problems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

MAXIMIZATION PPM14EM ON GRAPHS WITH EUM WEIGHTS CH0SEN FROM A NORVAL DISTRIBUTION

by

George S. Lueker

Department of Information and CaTputer Science University of California, Irvine Irvine, CA 92717

Technical Report #115

An extended abstract. of this report is tD appear in the Pro222~Es of the Tenth Annual ACM 'Spposium 'On of 'Computing (1978).

Keywords and phrases:

Randm graphs Optunzation problems Normal distribution Weighted graphs Probabilistic analysis Traveling salesman problem Cliques

+Supported by NSF Grant MCS77-04410.,

Abstract

~ie 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 whicn the bounds are tight include finding the optimum traveling salesman tour, finding a minimum cost spanning tree, am finding a heaviest clique on k vertices. We then discuss some greedy heuristic algorithms for these problems.

1. Introduction

Many results have been proven about the properties of randcm graphs. Scme of these JAV77, BE75, ER59, ER60, ER66, GM75, MOO, Po76, Wa77aj deal with graphs constructed by letting edges be present or absent according to some distribution; one then tries to estimate the probability that a subgraph of a given type will be present. We will call such a problem a subgraph existence problem. Another area of interest is algorithms on graphs in which all edges,are present, but weights are assigned to the edges according to some randan distribution; one then tries to find the heaviest (or lightest) subgraph of a given type. We will call such problems subgraph 2pLiLmization problems. For example, it a traveling salesman problem is constructed using the Euclidean distance between n points chosen from a uniform distribution in the unit square, then asymptotically the maximum solution is prcportional to V"n'j&ifl591; a very efficient algorithm has been designed whose expected behavior is asymptotically optimal [Ka761. The assignment problem for the case in.which weights are chosen from a uniform distribution has been studied by several people [Do69, Ku62, kaMj; Donath (Do691 has also

University of California, Irvine Page 1 Dec 31, 1978

Page 2 of 17

MAXIMIZATION PPM14EM ON GRAPHS WITH EUM WEIGHTS CH0SEN FROM A NORVAL DISTRIBUTION

considered the case in which the edge weights have a value x in 10,1) with probability proportional to xk for some k. In this paper we investigate the behavior of a number of optimization problejas on complete graphs with edge weights chosen imepenuentiy trom a normal distribution.

Throughout this paper, G . will be a random variable which is a complete, undirected, weighted, labeled graph on n vertices; we will ass...