Complexity of a class of nonlinear combinatorial problems related to their linear counterparts

DOI10.1016/0377-2217(94)90254-2MaRDI QIDQ1328652zbMATH OpenOpenAlexFDO

Authors Suresh P. Sethi, Wieslaw Kubiak

Publication date 26 July 1994

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(94)90254-2

zbMATH Keywords

NP-hardlinear combinatorial problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonlinear programming (90C30) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An NP-hardness result for nonlinear systems
• \(NP\)-hardness of linear multiplicative programming and related problems
• Some NP-complete problems in quadratic and nonlinear programming
• Complexity and algorithms for nonlinear optimization problems
• A polynomially solvable class of two-level nonlinear programming problems

Cites work

• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Completion time variance minimization on a single machine is difficult

Cited in

(6)

• On the Complexity of Computing Two Nonlinearity Measures
• A nonlinear lower bound on the practical combinational complexity
• On sets of linear forms of maximal complexity
• Non-deterministic linear hypersubstitutions
• Enumeration results on linear complexity profiles and lattice profiles
• Polynomial-Time Separation of a Superclass of Simple Comb Inequalities

This page was built for publication: Complexity of a class of nonlinear combinatorial problems related to their linear counterparts

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