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

DOI10.1016/0377-2217(94)90254-2zbMATH Open0805.90081OpenAlexW2017053537MaRDI QIDQ1328652FDOQ1328652

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Completion time variance minimization on a single machine is difficult

Cited In (6)

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

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)