TAILIEUCHUNG - Báo cáo toán học: "Generating a random sink-free orientation in quadratic time"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Generating a random sink-free orientation in quadratic time. | Generating a random sink-free orientation in quadratic time Henry Cohn Microsoft Research One Microsoft Way Redmond WA 98052-6399 cohn@ Robin Pemantle Department of Mathematics Ohio State University Columbus OH 43210 pemantle@ James Propp Department of Mathematics University of Wisconsin Madison WI 53706 propp@ Submitted May 1 2001 Accepted March 12 2002. MR Subject Classifications 60C05 68W20 Abstract A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer 1997 use Markov Chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time O m3 log 1 where m is the number of edges and the degree of approximation. Huber 1998 uses coupling from the past to obtain an exact sample in time O m4 . We present a simple randomized algorithm inspired by Wilson s cycle popping method which obtains an exact sample in mean time at most O nm where n is the number of vertices. 1. Introduction A common problem is to select a random sample efficiently from a large collection of combinatorial objects. There are many reasons one may wish to do this. One is to obtain an approximate count Jerrum and Sinclair JS showed that if one can generate nearly uniform samples then for each 0 one can obtain the cardinality of the collection to within a factor of 1 with probability 1 in just a little more time. When counting the collection is P-hard as in the case of properly -coloring a graph this may be the only reasonable way to count since it is unlikely that P-hard counting problems can This work was begun at the 1997 Workshop on Exact Simulation in Rebild Denmark funded by the European Science Foundation and completed at the 1998 Institute for Elementary Studies funded by the National Science Foundation . Cohn was supported by an NSF Graduate Research Fellowship and currently holds a five-year fellowship from

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.