wk@reef.cis.ufl.edu (Chip Klostermeyer) (06/20/91)
I would appreciate any references to a pseudo-polynomial time algorithm or a proof of NP-completeness in the strong sense for the zero-one integer programming problem. Also, any references to an algorithm for finding lower bounds for solutions to zero-one integer programming problems would be welcome. E-mail to wk@reef.cis.ufl.edu I will summarize to net. Thanks Chip Klostermeyer
spsl@cs.bham.ac.uk (Steven Lam) (06/21/91)
More NP-complete problems, I have developed a so-called "2 1/2-dimensional systolic array" which consists of a two tightly coupled mesh arrays. By allowing each cell to communicate with five neighbouring cells (i.e. four on the same layer and one on the adjacent layer), I have developed a reconfiguration scheme to recover a defected array. Later on, I found that the connectivity constraint will have to be relaxed further, i.e. diagonal connections between cells are allowed, the resultant array gives a high percentage of fault tolerance. Now, the question is whether it is a NP-complete problem to simulation this reconfigurable array? I will be gratefull to hear your comments. Thanks Stephen