On the conductance of order Markov chains

DOI10.1007/BF00385809zbMath0736.06002MaRDI QIDQ1182035

Leonid G. Khachiyan, Alexander V. Karzanov

Publication date: 27 June 1992

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

isoperimetric inequalityconductancelinear extensions for posetsorder Markov chainssorting of posetsuniform generators

Mathematics Subject Classification ID

Partial orders, general (06A06)

Related Items (31)

Fast perfect sampling from linear extensions ⋮ The computational complexity of calculating partition functions of optimal medians with Hamming distance ⋮ Isoperimetric problems for convex bodies and a localization lemma ⋮ Upper Bounds on Mixing Time of Finite Markov Chains ⋮ Sequence Covering Arrays and Linear Extensions ⋮ Effective Poset Inequalities ⋮ Mixing time for Markov chain on linear extensions ⋮ On random generation of fuzzy measures ⋮ Mixing times of lozenge tiling and card shuffling Markov chains ⋮ Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets ⋮ Poincaré inequality in mean value for Gaussian polytopes ⋮ On the conductance of order Markov chains ⋮ Counting linear extensions ⋮ The combinatorics of tandem duplication ⋮ Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Combinatorial Markov chains on linear extensions ⋮ Using TPA to count linear extensions ⋮ Bottom-up: a new algorithm to generate random linear extensions of a poset ⋮ Log-concave poset inequalities ⋮ Rank tests from partially ordered data using importance and MCMC sampling methods ⋮ On the polytope of 3-tolerant fuzzy measures ⋮ Applying Young diagrams to 2-symmetric fuzzy measures with an application to general fuzzy measures ⋮ An approximation algorithm for random generation of capacities ⋮ Counting and sampling SCJ small parsimony solutions ⋮ An improvement of random node generator for the uniform generation of capacities ⋮ Unnamed Item ⋮ Finding Rumor Sources on Random Trees ⋮ Balanced pairs in partial orders ⋮ Faster random generation of linear extensions ⋮ Similarity of personal preferences: Theoretical foundations and empirical analysis

Cites Work

• Unnamed Item
• Two poset polytopes
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On the conductance of order Markov chains
• How good is the information theory bound in sorting?
• Existence and regularity almost everywhere of solutions to elliptic variational problems with constraints

This page was built for publication: On the conductance of order Markov chains