DocumentCode :
1970818
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
fYear :
2002
fDate :
2002
Firstpage :
77
Lastpage :
83
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Computing Systems and Applications, 2002. Proceedings. 16th Annual International Symposium on
Print_ISBN :
0-7695-1626-2
Type :
conf
DOI :
10.1109/HPCSA.2002.1019137
Filename :
1019137
Link To Document :
بازگشت