zbMATH — the first resource for mathematics

On the complexity of four polyhedral set containment problems. (English) Zbl 0581.90060
A nonempty closed convex polyhedron X can be represented either as \(X=\{x:\) Ax\(\leq b\}\), where (A,b) are given, in which case X is called an H-cell, or in the form \(X=\{x:\) \(x=U\lambda +V\mu\), \(\sum \lambda_ j=1\), \(\lambda\geq 0\), \(\mu\geq 0\}\), where (U,V) are given, in which case X is called a W-cell. This note discusses the computational complexity of certain set containment problems. The problems of determining if \(X\not\subseteq Y\), where (i) X is an H-cell and Y is a closed solid ball, (ii) X is an H-cell and Y is a W-cell, or (iii) X is a closed solid ball and Y is a W-cell, are all shown to be NP-complete, essentially verifying a conjecture of B. C. Eaves and the first author [ibid. 23, 138-147 (1982; Zbl 0479.90064)]. Furthermore, the problem of determining whether there exists an integer point in a W-cell is shown to be NP-complete, demonstrating that regardless of the representation of X as an H-cell or W-cell, this integer containment problem is NP-complete.

90C10 Integer programming
52Bxx Polytopes and polyhedra
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] B.C. Eaves and R.M. Freund, ”Optimal scaling of balls and polyhedra”,Mathematical Programming 23 (1982) 138–147. · Zbl 0479.90064 · doi:10.1007/BF01583784
[2] F.R. Gantmacher,Matrix theory, vol. 1 (Chelsea, New York, 1959). · Zbl 0085.01001
[3] M.R. Garey and D.S. Johnson,Computers and intractability (W.H. Freeman, San Francisco, 1979).
[4] R.M. Karp, ”Reducibility among combinatorial problems”, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of computer computations (Plenum Press, New York, 1972) pp. 85–103.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.