We describe an application of distributed processing to approximating the solution to certain NP-complete problems in Combinatorial Optimization. The basic technique employed is known as Simulated Annealing and consists of a stochastic search inspired in the principles of Statistical Physics. A wide class of problems for which the method can be parallelized is characterized. For these problems the search can act simultaneously upon a relatively large subset of the variables involved. The distributed implementation we describe associates a dedicated processor with each variable in the problem and connects processors to one another sparsely. The achievable degree of concurrency depends on how the several variables in the problem are interrelated. Among the problems amenable to this parallelization is the Minimum Vertex Cover Problem. The proposed implementation raises two other questions which are potentially relevant to other issues in distributed processing as well. These are the scheduling of processors for operation and the retrieval of the solution found. In addressing the latter question, it is shown that the retrieval process can be carried out through efficient network flow computations on precedence graphs. o 1989 Academic Press, Inc.