Utilizing shelve slots: Sufficiency conditions for some easy instances of hard problems

DOI10.1006/JCOM.1994.1010MaRDI QIDQ1333241zbMATH OpenOpenAlexFDO

Authors Moshe Dror, Benjamin T. Smith, Martin Trudeau

Publication date 5 April 1995

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.1994.1010

zbMATH Keywords

existence of a solutionnonnegative linear diophantine equationsNP- complete problemspolynomial time

Mathematics Subject Classification ID

Diophantine equations (11D99) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Efficiently solvable special cases of hard combinatorial optimization problems
• Approximation schemes for knapsack problems with shelf divisions
• On the complexity of Slater's problems
• Shellings from relative shellings, with an application to NP-completeness
• Theory and Applications of Satisfiability Testing
• Complexity results for storage loading problems with stacking constraints
• Simple lifted cover inequalities and hard knapsack problems
• scientific article; zbMATH DE number 4031399

Cited in

(2)

• PACKING SHELVES WITH ITEMS THAT DIVIDE THE SHELVES' LENGTH: A CASE OF A UNIVERSAL NUMBER PARTITION PROBLEM
• Universal number partition problem with divisibility

This page was built for publication: Utilizing shelve slots: Sufficiency conditions for some easy instances of hard problems

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