Extending NC and RNC algorithms (Q1263974)

N. Megiddo describes a technique for extending NC and RNC algorithms for some problems into NC and RNC algorithms, respectively, solving more general parametric problems. The presentation is based on the computational model of arithmetic circuits, i.e. acyclic directed graphs the nodes of which can perform any of the basic arithmetic operations or a maximum or a minimum operation. It is shown that this technique can be used to prove that a broad range of optimization problems is in NC, in particular max-min and min-ratio problems arising e.g. in scheduling.