Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions

DOI10.1137/S0097539702411915zbMath1101.68044MaRDI QIDQ4651531

Alistair Sinclair, Ben Morris

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Markov chainsrandom walksknapsack problemhypercubesrandom samplingrandom permutationsbalanced permutations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (21)

On approximating weighted sums with exponentially many terms ⋮ Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ Spectral analysis of finite Markov chains with spherical symmetries ⋮ Heat-bath random walks with Markov bases ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Faster FPTASes for counting and random generation of knapsack solutions ⋮ Approximately counting and sampling knowledge states ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ Unnamed Item ⋮ Pattern hit-and-run for sampling efficiently on polytopes ⋮ On the computational complexity of the probabilistic traveling salesman problem with deadlines ⋮ A Faster FPTAS for #Knapsack ⋮ The mixing time of switch Markov chains: a unified approach ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ A multivariate statistical approach to predict COVID-19 count data with epidemiological interpretation and uncertainty quantification ⋮ Average mixing in quantum walks of reversible Markov chains ⋮ The Markov chain Monte Carlo revolution ⋮ Estimating the probability of meeting a deadline in schedules and plans ⋮ Sequential stratified splitting for efficient Monte Carlo integration

This page was built for publication: Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions