Re: What is general term for this problem?

On Thu, 16 Sep 2004 12:34:23 -0400, Kenneth Downs wrote:
>
> I wonder if anyone can tell me the name of the general case of a particular
> operation. I have not seen it discussed here in my lurking.
>
> I first saw the operation in the Allocation process of an ERP package, but
> the problem is easy enough to generalize. The particular thing about this
> problem is that it does not seem to be solvable with a single SELECT or
> read, it seems impossible to avoid loop-based procedural code.
>
> Consider a table representing supply, such as production or purchase orders,
> and another table representing demand, such as sales orders. The task is
> to use a set of rules to determine for each order if supply will meet
> demand, and to identify unmet demand and unnecessary supply.

That would be '(maximum) bipartite matching' of which the 'marriage problem' is probably the simplest example. These are special cases of 'constraint satisfaction problems' but where these are in general NP-hard the bipartite matching problems can often be solved in polynomial time. The usual way of showing this is by translating it to the problem of finding the maximal flow in a certain network and solving it with the Ford-Fulkerson method.

For some interesting slides on this:

        http://www.comp.nus.edu.sg/~ooiwt/slides/2004-cs3233-graph2.ppt

But these algorithms are usually in the form of fixpoint algorithms (i.e., repeat a certain optimization until you can no longer optimize) which are not implementable in a single select without using recursion.

• Jan Hidders