6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I recently asked a question that turned out to be equivalent: cstheory.stackexchange.com/questions/42705/… I found some interesting references, but nothing definitive yet. $\endgroup$ – Lorenzo Najt Apr 14 '19 at 4:30
  • $\begingroup$ I think I was able to show it is NP-hard. Take a look and see if you believe my argument. :-) $\endgroup$ – Lorenzo Najt Apr 20 '19 at 5:17
  • 1
    $\begingroup$ It is $NP$-hard. See updated answer. $\endgroup$ – Lorenzo Najt Nov 13 '19 at 0:22
  • $\begingroup$ @LorenzoNajt- Thanks for the update! $\endgroup$ – Steve Huntsman Nov 13 '19 at 15:37
5
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – Steve Huntsman Jan 2 '19 at 14:52
  • $\begingroup$ ...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." $\endgroup$ – Steve Huntsman Jan 2 '19 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.