Inverse problems of some NP-complete problems

DOI10.1007/11496199_45MaRDI QIDQ5710144zbMATH OpenOpenAlexFDO

Authors Siming Huang

Publication date 30 November 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b137095

zbMATH Keywords

integer programminginverse problemknapsack problempseudo-polynomial algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The inverse \(\{0,1\}\)-knapsack problem: theory, algorithms and computational experiments
• The inverse-parametric knapsack problem
• scientific article; zbMATH DE number 5823945
• scientific article; zbMATH DE number 4031399
• Inverse NP problems

Cited in

(13)

• Cutting plane algorithms for the inverse mixed integer linear programming problem
• A useful transform of standard input data for a classical NP-complete problem
• On some badly-solved problems with invexity
• Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem
• Inverse multi-objective combinatorial optimization
• The inverse \(\{0,1\}\)-knapsack problem: theory, algorithms and computational experiments
• \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete
• On the complexity of inverse mixed integer linear optimization
• About some features of the transformed problems images
• Inverse Unfold Problem and Its Heuristic Solving
• All superlinear inverse schemes are coNP-hard
• Inverse of the Gomory corner relaxation of integer programs
• Inverse integer programming

This page was built for publication: Inverse problems of some NP-complete problems

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