On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]

DOI10.1016/J.TCS.2006.07.016MaRDI QIDQ860874zbMATH OpenOpenAlexFDO

Authors Fenghui Zhang, Jianer Chen

Publication date 9 January 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.016

zbMATH Keywords

complexityfixed parameter tractableW-hierarchy

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Production models (90B30)

Recommendations

• Algorithmic Applications in Management
• The periodic joint replenishment problem is strongly \(\mathcal{NP} \)-hard
• Computational complexity of uncapacitated multi-echelon production planning problems
• Analysis of fractional covering of some supply management problems
• On the computational complexity of uncapacitated multi-plant lot-sizing problems

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• Linear FPT reductions and computational lower bounds
• Network optimization in supply chain management and financial engineering: An annotated bibliography
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• Supply chain management: Models, applications, and research directions
• The Turing way to parameterized complexity
• Vertex cover: Further observations and further improvements

Cited in

(9)

• On the complexity of solution extension of optimization problems
• The complexity of dependency detection and discovery in relational databases
• On the parameterised complexity of string morphism problems
• Algorithmic Applications in Management
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Multiple commodity supply chain with maximal covering approach in a three layer structure
• A multi-parameter analysis of hard problems on deterministic finite automata
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• Invited talks

This page was built for publication: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]

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