Adjacency of the 0-1 knapsack problem

DOI10.1016/0305-0548(92)90019-2MaRDI QIDQ1195107zbMATH OpenOpenAlexFDO

Authors Daniel Geist, E. 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

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

Recommendations

• scientific article; zbMATH DE number 4005976
• Sensitivity analysis for knapsack problems: Another negative result
• The quadratic 0-1 knapsack problem with series-parallel support
• The complexity of the 0/1 multi-knapsack problem
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation

Cites work

• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 3687081 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A New Algorithm for the 0-1 Knapsack Problem
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Computing Partitions with Applications to the Knapsack Problem
• Easily Computable Facets of the Knapsack Polytope
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the Knapsack Polytope From Minimal Covers
• Facets of the knapsack polytope
• Heuristic algorithms for the multiple knapsack problem
• On certain polytopes associated with graphs
• The adjacency relation on the traveling salesman polytope is NP-Complete
• The complexity of lifted inequalities for the knapsack problem

Cited in

(7)

• Connectedness of efficient solutions in multiple objective combinatorial optimization
• Knapsack polytopes: a survey
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• Shortest reconfiguration of perfect matchings via alternating cycles
• The 1-Neighbour Knapsack Problem
• On the skeleton of the polytope of pyramidal tours
• scientific article; zbMATH DE number 847586 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1195107)