KOBV Portal

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Online Resource

Stochastic Billiards for Sampling from the Boundary of a Convex Set

Dieker, A. B. ; Vempala, Santosh S.

Institute for Operations Research and the Management Sciences (INFORMS) ; 2015

In: Mathematics of Operations Research Vol. 40, No. 4 ( 2015-10), p. 888-901

add to watchlist on the watchlist

Details

In: Mathematics of Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 40, No. 4 ( 2015-10), p. 888-901

Abstract: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.

Type of Medium: Online Resource

ISSN: 0364-765X , 1526-5471

URL: Article

DOI: 10.1287/moor.2014.0701

Language: English

Publisher: Institute for Operations Research and the Management Sciences (INFORMS)

Publication Date: 2015

detail.hit.zdb_id: 2004273-5

detail.hit.zdb_id: 195683-8

SSG: 3,2