Mixing Time of Markov chain of the Knapsack Problem

Koko K. Kayibi, S. Pirzada, Carrie Rutherford

Type: Preprint

Publication Date: 2018-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.1803.06914

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	On the mixing set with a knapsack constraint	2016	Ahmad Abdi Ricardo Fukasawa
+	Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures	2004	Fabio Martinelli
+	Problemas de Knapsack 0-1 con una restricción adicional	1988	Jaume Barceló Bugeda Elena Fernández
+ PDF Chat	A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions	2012	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	Integer Knapsacks and the Frobenius Problem	2011	Lenny Fukshansky
+ PDF Chat	Exact Counting and Sampling of Optima for the Knapsack Problem	2021	Jakob Bossek Aneta Neumann Frank Neumann
+	Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)	2016	Venkatesan Guruswami
+	The growth of multi-constraint random knapsacks with large right-hand sides of the constraints	1997	K. Szkatuz̵a
+	Faster markov chain monte carlo algorithms for the permanent and binary contingency tables	2006	Eric Vigoda Ivona Bezáková
+	A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions	2010	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions	2010	Daniel Štefankovič Santosh Vempala Eric Vigoda
+ PDF Chat	A randomized version of the Collatz <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mn>3</mml:mn><mml:mi>x</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:math> problem	2015	Aristides V. Doumas Vassilis G. Papanicolaou
+	Canonical Paths for MCMC: from Art to Science	2015	Lingxiao Huang Pinyan Lu Chihao Zhang
+	Some examples and problems in Markov chains	1985	Kepha Okari Marube
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair
+ PDF Chat	Random assignment and shortest path problems	2006	Johan Wästlund
+ PDF Chat	Random knapsacks with many constraints	1994	Kenneth Schilling
+	Complexity of counting the optimal solutions	2009	Miki Hermann Reinhard Pichler
+	Canonical paths for MCMC: from art to science	2016	Lingxiao Huang Pinyan Lu Chihao Zhang
+	Canonical Paths for MCMC: from Art to Science	2015	Lingxiao Huang Pinyan Lu Chihao Zhang

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (6)

Action	Title	Year	Authors
+	An improved estimator of the finite population mean in simple random sampling	2011	Lovleen Kumar Grover Paramdeep Kaur
+	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions	2004	Ben Morris Alistair Sinclair
+ PDF Chat	Approximating the Permanent	1989	Mark Jerrum Alistair Sinclair
+	Markov Chain Algorithms for Planar Lattice Structures	2001	Michael Luby Dana Randall Alistair Sinclair
+	Sampling contingency tables	2017	Koko K. Kayibi S. Pirzada T. A. Chishti
+	T-tetrominoes tiling's Markov chain mixes fast	2017	Koko K. Kayibi S. Pirzada