Title :
The characterization of parallel real-time optimization problems
Author :
Bruda, Stefan D. ; Akl, Selim G.
Author_Institution :
Dept. of Comput. & Inf. Sci., Queen´´s Univ., Kingston, Ont., Canada
Abstract :
We identify the class of optimization problem expressible as independence systems that can be solved in real time using a parallel machine with polynomially bounded resources as being exactly the class of matroid for which the size of the optimal solution can be computed in parallel real time. We also extend previous results, showing that the solution obtained by a parallel algorithm is arbitrarily better than the solution reported by a sequential one not only for the real-time minimum-weight spanning tree (as previously known). Indeed, we show that, for all practical purposes, such a property does in fact hold for any optimization problem that falls into the aforementioned class.
Keywords :
computational complexity; parallel algorithms; complexity theory; formal methods; independence systems; matroids; minimum-weight spanning tree; optimization problem; parallel algorithm; parallel complexity; parallel machine; Complexity theory; Computational modeling; Concurrent computing; Distributed computing; Information science; Parallel algorithms; Parallel machines; Polynomials; Real time systems; Time factors;
Conference_Titel :
High Performance Computing Systems and Applications, 2002. Proceedings. 16th Annual International Symposium on
Print_ISBN :
0-7695-1626-2
DOI :
10.1109/HPCSA.2002.1019137