I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO questions Uniformly Sampling from Convex Polytopes and Is it possible to sample uniformly on the surface of a high-dimensional polytope?. A bit of poking around Google Scholar hasn't turned anything up.
Asked
Active
Viewed 347 times
7
-
2I recently asked a question that turned out to be equivalent: https://cstheory.stackexchange.com/questions/42705/can-one-efficiently-uniformly-sample-a-neighbor-of-a-vertex-in-the-graph-of-a-po I found some interesting references, but nothing definitive yet. – Elle Najt Apr 14 '19 at 04:30
-
I think I was able to show it is NP-hard. Take a look and see if you believe my argument. :-) – Elle Najt Apr 20 '19 at 05:17
-
1It is $NP$-hard. See updated answer. – Elle Najt Nov 13 '19 at 00:22
-
@LorenzoNajt- Thanks for the update! – Steve Huntsman Nov 13 '19 at 15:37
1 Answers
5
Here is one efficient approach, performing a random walk with a rapid mixing time, that has been implemented for a particular class of polytopes, but which might well be adaptable to a more general setting: Random Walks on the Vertices of Transportation Polytopes (2008).
Carlo Beenakker
- 177,695
-
Interesting bit from the first page: "Markov chain Monte Carlo (MCMC) has not been well explored as a means of sampling, or approximately counting, vertices of general polytopes." – Steve Huntsman Jan 02 '19 at 14:52
-
...and from the conclusions: "The question of whether we can sample vertices of a general [transportation polytope], when the number of sources is not constant, is still open." – Steve Huntsman Jan 02 '19 at 14:53