Hit-and-run from a corner. (English) Zbl 1192.68371
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 310-314, electronic only (2004).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 60G50 | Sums of independent random variables; random walks |
References:
| [1] | M. E. Dyer and A. M. Frieze: Computing the volume of a convex body: a case where randomness provably helps, Proc. of AMS Symposium on Probabilistic Combinatorics and Its Applications, 1991, 123-170. |
| [2] | R. Kannan and L. Lovász: Faster mixing through average conductance, Proc. of STOC, 1999, 282-287. 10.1145/301250.301317 · Zbl 1345.60078 |
| [3] | R. Kannan, L. Lovász and M. Simonovits: Isoperimetric problems for convex bodies and a localization lemma, J. Discr. Comput. Geom. 13 (1995) 541-559. · Zbl 0824.52012 |
| [4] | R. Kannan, L. Lovász and M. Simonovits: Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures and Algorithms 11 (1997), 1-50. 10.1002/(SICI)1098-2418(199708)11:1 · Zbl 0895.60075 |
| [5] | L. Lovász: Hit-and-run mixes fast, Math. Prog. 86 (1998), 443-461. · Zbl 0946.90116 |
| [6] | L. Lovász and M. Simonovits: Random walks in a convex body and an improved volume algorithm, Random Structures and Alg. 4 (1993), 359-412. · Zbl 0788.60087 |
| [7] | L. Lovász and S. Vempala: The geometry of logconcave functions and an O*(n3) sampling algorithm, Microsoft Research Tech. Rep. MSR-TR-2003-04. Available at: http://www-math. mit. edu/ vempala/papers/logcon-ball. ps |
| [8] | L. Lovász and S. Vempala: Hit-and-run is fast and fun, Microsoft Research Tech. Rep. MSR-TR-2003-05. Available at http://www-math. mit. edu/ vempala/papers/logcon-hitrun. ps |
| [9] | L. Lovász and S. Vempala: Simulated annealing in convex bodies and an O*(n4) volume algorithm. Proc. of FOCS, 2003, 650-659. |
| [10] | R. L. Smith: Efficient Monte-Carlo procedures for generating points uniformly distributed over bounded regions, Operations Res. 32, (1984), 1296-1308. · Zbl 0552.65004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
