A FAST BIPARTITE NETWORK FLOW ALGORITHM FOR SELECTIVE ASSEMBLY

Bipartite network flow problems naturally arise in applications such a s selective assembly and preemptive scheduling. This paper presents fa st algorithms for these problems that take advantage of special proper ties of the associated bipartite networks. We show a connection betwee n selective assembly and the earliest due date (EDD) scheduling rule, and we show that EDD can be implemented in linear time when the data a re already sorted. Our main result uses a Monge property to get a line ar-time algorithm for selective assembly with a monotone convex loss f unction. (C) 1998 Elsevier Science B.V. All rights reserved.