Extending NC and RNC algorithms
type: Item
instance of: scholarly article
title: Extending NC and RNC algorithms
zbMATH Open document ID: 0688.68042
DOI: 10.1007/BF01553905
author: Nimrod Megiddo
published in: Algorithmica
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 4128388
zbMATH Keywords: circuit complexity
zbMATH Keywords: probabilistic circuits
zbMATH Keywords: poly-log depth
zbMATH Keywords: parametric problems
reviewed by: Hartmut Schmeck
MaRDI profile type: Publication
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Finding Least-Distances Lines
cites work: New Results on the Complexity of p-Centre Problems
cites work: An O(nlogn) randomizing algorithm for the weighted euclidean 1-center problem
description: scientific article; zbMATH DE number 4128388