A Heuristic Method for Solving the Problem of Partitioning Graphs with
  Supply and Demand
  In this paper we present a greedy algorithm for solving the problem of the
maximum partitioning of graphs with supply and demand (MPGSD). The goal of the
method is to solve the MPGSD for large graphs in a reasonable time limit. This
is done by using a two stage greedy algorithm, with two corresponding types of
heuristics. The solutions acquired in this way are improved by applying a
computationally inexpensive, hill climbing like, greedy correction procedure.
In our numeric experiments we analyze different heuristic functions for each
stage of the greedy algorithm, and show that their performance is highly
dependent on the properties of the specific instance. Our tests show that by
exploring a relatively small number of solutions generated by combining
different heuristic functions, and applying the proposed correction procedure
we can find solutions within only a few percent of the optimal ones.
