[comp.theory] Help with an NP-complete problem

STYLIADH@GRPATVX1.BITNET (12/15/89)

I am dealing with the following NP_complete
Let A be a three dimensional matrix A[1..n][1..m][1..w], of INTEGERS,
xn[1..n] a one dimensional matrix of INTEGERS and N[1..n] a one dimensional
matrix of integers in the range 1..n.
Given the sums

     n
(A) SUM A[i][j][k]  foreach j in [1,m] ,k in [1,w].
    i=1


     m
(B) SUM A[i][j][k] foreach i in [1,n],k in [1,w].
    j=1

     w
(C) SUM A[i][j][k] foreach i in [1,n],j in [1,m]
    k=1

and the fact that :
from the n elements A[i][j][k], j in [1,m],k in [1,w],N[i] of them have a
known integer value xn[i] and n-N[i] of them have the value xn[i]+1.
xn[i]>=0 foreach i.
A[i][j][k] >=0 foreach i,j,k.

which are the elements A[i][j][k] foreach i in [1,n],j in [1,m],k in [1,w]?



The problem obviously is NP-complete.

I wonder if anyone can help me with aproximation methods or clever heuristics
or anything.

I would  welcome any coments,bibliography,ideas anything.


  Many thanks.