Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
From MaRDI portal
Publication:4651531
DOI10.1137/S0097539702411915zbMath1101.68044MaRDI QIDQ4651531
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Markov chainsrandom walksknapsack problemhypercubesrandom samplingrandom permutationsbalanced permutations
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 (19)
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 ⋮ 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
