%0 Book Section %1 springerlink:10.1007/3-540-57899-4_37 %A Holloway, N. %A Ravindran, S. %A Gibbons, A. %B Graph-Theoretic Concepts in Computer Science %C Berlin / Heidelberg %D 1994 %E van Leeuwen, Jan %I Springer %K complete.graph matching perfect.matching triangle.inequality %P 11-20 %R 10.1007/3-540-57899-4_37 %T Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality %U http://dx.doi.org/10.1007/3-540-57899-4_37 %V 790 %X We describe an O ( log 3 n ) time NC approximation algorithm for the CREW P-RAM, using n 3 / log n processors with a 2log 3 n performance ratio, for the problem of finding a minimum-weight perfect matching in complete graphs satisfying the triangle inequality. The algorithm is conceptually very simple and has a work measure within a factor of log 2 n of the best exact sequential algorithm. This is the first NC approximation algorithm for the problem with a sub-linear performance ratio. As was the case in the development of sequential complexity theory, matching problems are on the boundary of what problems might ultimately be described as tractable for parallel computation. Future work in this area is likely to decide whether these ought to be regarded as those problems in NC or those problems in RNC . %@ 978-3-540-57899-4

@incollection{springerlink:10.1007/3-540-57899-4_37, abstract = {We describe an O ( log 3 n ) time NC approximation algorithm for the CREW P-RAM, using n 3 / log n processors with a 2log 3 n performance ratio, for the problem of finding a minimum-weight perfect matching in complete graphs satisfying the triangle inequality. The algorithm is conceptually very simple and has a work measure within a factor of log 2 n of the best exact sequential algorithm. This is the first NC approximation algorithm for the problem with a sub-linear performance ratio. As was the case in the development of sequential complexity theory, matching problems are on the boundary of what problems might ultimately be described as tractable for parallel computation. Future work in this area is likely to decide whether these ought to be regarded as those problems in NC or those problems in RNC .}, added-at = {2012-09-16T16:21:22.000+0200}, address = {Berlin / Heidelberg}, affiliation = {University of Warwick Department of Computer Science CV4 7AL Coventry UK CV4 7AL Coventry UK}, author = {Holloway, N. and Ravindran, S. and Gibbons, A.}, biburl = {https://www.bibsonomy.org/bibtex/2696e2344509683a975eb7562583b088d/ytyoun}, booktitle = {Graph-Theoretic Concepts in Computer Science}, doi = {10.1007/3-540-57899-4_37}, editor = {van Leeuwen, Jan}, interhash = {167139b12d02d96b4b584f620c44ff2f}, intrahash = {696e2344509683a975eb7562583b088d}, isbn = {978-3-540-57899-4}, keyword = {Computer Science}, keywords = {complete.graph matching perfect.matching triangle.inequality}, pages = {11-20}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2012-09-16T21:29:03.000+0200}, title = {Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality}, url = {http://dx.doi.org/10.1007/3-540-57899-4_37}, volume = 790, year = 1994 }