Adjacency of the 0-1 knapsack problem

DOI10.1016/0305-0548(92)90019-2zbMath0758.90059OpenAlexW2017122944MaRDI QIDQ1195107

Daniel Geist, Ervin Y. Rodin

Publication date: 5 October 1992

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0305-0548(92)90019-2

zbMATH Keywords

NP-completeadjacency0-1 knapsack polytope

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Boolean programming (90C09)

Related Items (5)

Knapsack polytopes: a survey ⋮ On the Skeleton of the Polytope of Pyramidal Tours ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Connectedness of efficient solutions in multiple objective combinatorial optimization ⋮ The common face of some 0/1-polytopes with NP-complete nonadjacency relation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristic algorithms for the multiple knapsack problem
• The complexity of lifted inequalities for the knapsack problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• On certain polytopes associated with graphs
• Easily Computable Facets of the Knapsack Polytope
• A New Algorithm for the 0-1 Knapsack Problem
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Computing Partitions with Applications to the Knapsack Problem
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Facets of the Knapsack Polytope From Minimal Covers

This page was built for publication: Adjacency of the 0-1 knapsack problem