On product covering in supply chain models: Natural complete problems for W[3] and W [4] Conference Paper uri icon

abstract

  • The field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. In this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes W[3] and W[4] in parameterized complexity theory. This seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i.e., the W-hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. Our results also derive strong computational lower bounds and inapproximability for these optimization problems. Springer-Verlag Berlin Heidelberg 2005.

name of conference

  • Algorithmic Applications in Management, First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings

published proceedings

  • Lecture Notes in Computer Science

author list (cited authors)

  • Chen, J., & Zhang, F.

complete list of authors

  • Chen, J||Zhang, F

publication date

  • September 2005