Hidden Hamiltonian Cycle Recovery via Linear Programming
From MaRDI portal
Publication:5130484
DOI10.1287/opre.2019.1886zbMath1445.90007arXiv1804.05436OpenAlexW2997404769WikidataQ126413191 ScholiaQ126413191MaRDI QIDQ5130484
Yihong Wu, Jiaming Xu, Jian Ding, Vivek Bagaria, David N. C. Tse
Publication date: 4 November 2020
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1804.05436
traveling salesman problempolyhedral combinatoricslarge deviations theoryfractional 2-factor linear programming
Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Genetics and epigenetics (92D10)
Related Items
Iterative algorithm for discrete structure recovery, Reconstruction of line-embeddings of graphons, The planted matching problem: sharp threshold and infinite-order phase transition, The planted k-factor problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Minimax rates of community detection in stochastic block models
- Semidefinite programming relaxations for the quadratic assignment problem
- Random Laplacian matrices and convex relaxations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- DNA physical mapping and alternating Eulerian cycles in colored graphs
- A new bound for the ratio between the 2-matching problem and its linear programming relaxation
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Convex Relaxations and Integrality Gaps
- Sum-of-squares Lower Bounds for Planted Clique
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- NON-NULL RANKING MODELS. I
- Odd Minimum Cut Sets and b-Matchings Revisited
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- Large Cliques Elude the Metropolis Process
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Finding hidden hamiltonian cycles
- 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
- Stringing High-Dimensional Data for Functional Analysis
- Community detection thresholds and the weak Ramanujan property
- Integer Programming: Methods, Uses, Computations
- Paths, Trees, and Flowers
- Information Theory of DNA Shotgun Sequencing
- Collective dynamics of ‘small-world’ networks
- Solution of a Large-Scale Traveling-Salesman Problem
- Maximum matching and a polyhedron with 0,1-vertices
- Abundance matrices and seriation in archaeology
- The Traveling-Salesman Problem and Minimum Spanning Trees
