Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra

C.G.E. Boender, R.J. Caron, J.F. McDonald, A.H.G. Rinnooy Kan, H.E. Romeijn, R.L. Smith, J. Telgen, A.C.F. Vorst

Research output: Contribution to journalArticleProfessional

64 Downloads (Pure)

Abstract

In this paper, we study the so-called shake-and-bake algorithms which, as far as we know, provide the only practical way of generating (asymptotically) uniform points on the boundary as of a fully-dimensional polyiope S. The fact that the points are uniformly distributed means that, in the long run, all subsets of as of equal size will be visited equally often, and subsets with positive measure will be visited with probability one. Part of the material that we present in this paper may be found in more detail in the technical reports of Boender et al. ( l 988a, b ). For the so-called hit-and-run algorithms, which generate asymptotically uniform points on the interior of S, we refer to Smith ( 1984) and Berbee et al. ( 1987).
Original languageEnglish
Pages (from-to)945-954
Number of pages10
JournalOperations research
Volume39
Issue number6
DOIs
Publication statusPublished - 1991

Fingerprint Dive into the research topics of 'Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra'. Together they form a unique fingerprint.

Cite this