Sampling and integration of near log-concave functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sampling and integration of near log-concave functions

Full text

Pdf (637 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 156 - 163

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

David Applegate
Ravi Kannan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 46, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103439 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BONNESEN, T., AND FENCHEL, W. Theorie der konvexen KSrper. Springer, Berlin, 1934.
	2	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
	3	GROTSCHEL, M., Lovi.sz, L., AND SCHRIJVER, A. Geometric Algorithms and Combinatomal Optimization. Springer-Verlag, Berlin, 1988.
	4	HOEFFDING, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (1963), 13-30.
	5	LENSTRA, H. W. Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 4 (1983), #38-548.
	6	LovAsz, L., AND SIMONOVITS, M. The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In Proceedings of the Thirty-First IEEE Symposium on Foundations of Computer Science (1990), pp. 346-355.
	7	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]

CITED BY 11

	Wu-Lin Chen , Colm Art O'Cinneide, Towards a polynomial-time randomized algorithm for closed product-form networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.3, p.227-253, July 1998
	Lov K. Grover, Rapid sampling though quantum computing, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.618-626, May 21-23, 2000, Portland, Oregon, United States
	Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Adam Kalai , Santosh Vempala, Efficient algorithms for universal portfolios, The Journal of Machine Learning Research, 3, 3/1/2003
	László Lovász , Santosh Vempala, Simulated annealing in convex bodies and an O^*(n⁴) volume algorithm, Journal of Computer and System Sciences, v.72 n.2, p.392-417, March 2006
	Thomas D. Nielsen , Finn V. Jensen, Learning a decision maker's utility function from (possibly) inconsistent behavior, Artificial Intelligence, v.160 n.1, p.53-78, December 2004
	László Lovász , Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms, v.30 n.3, p.307-358, May 2007
	Peter Mathé , Erich Novak, Simple Monte Carlo and the Metropolis algorithm, Journal of Complexity, v.23 n.4-6, p.673-696, August, 2007
	Alexander Barvinok, Enumerating contingency tables via random permanents, Combinatorics, Probability and Computing, v.17 n.1, p.1-19, January 2008
	Deepak Ramachandran , Eyal Amir, Bayesian inverse reinforcement learning, Proceedings of the 20th international joint conference on Artifical intelligence, p.2586-2591, January 06-12, 2007, Hyderabad, India
	Adam Tauman Kalai , Santosh Vempala, Simulated Annealing for Convex Optimization, Mathematics of Operations Research, v.31 n.2, p.253-266, February 2006