File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: An approximation solution for the 2-median problem on two-dimensional meshes

TitleAn approximation solution for the 2-median problem on two-dimensional meshes
Authors
Tse, SSHLau, FCM
KeywordsApproximation Algorithms
Distributed and Parallel Computing
Location Problem
Mesh
P-Median
Parallel Computers
Issue Date2005
Citation
The 19th International Conference on Advanced Information Networking and Applications (AINA 2005), Taipei, Taiwan, 28-30 March 2005. In International Conference on Advanced Information Networking and Applications Proceedings, 2005, v. 2, p. 457-460 How to Cite?
DOI: http://dx.doi.org/10.1109/AINA.2005.92
AbstractWe study the p-median problem which is one of the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(m 2 + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5+δ on the communication cost, where m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, m ≥ n, q the number of demand points, and 6 is some positive constant which can be as small as needed. © 2005 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/151883
ISSN
1550-445X
2020 SCImago Journal Rankings: 0.239
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorTse, SSHen_US
dc.contributor.authorLau, FCMen_US
dc.creatorsml 160105 - amend-
dc.date.accessioned2012-06-26T06:30:21Z-
dc.date.available2012-06-26T06:30:21Z-
dc.date.issued2005en_US
dc.identifier.citationThe 19th International Conference on Advanced Information Networking and Applications (AINA 2005), Taipei, Taiwan, 28-30 March 2005. In International Conference on Advanced Information Networking and Applications Proceedings, 2005, v. 2, p. 457-460en_US
dc.identifier.issn1550-445Xen_US
dc.identifier.urihttp://hdl.handle.net/10722/151883-
dc.description.abstractWe study the p-median problem which is one of the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(m 2 + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5+δ on the communication cost, where m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, m ≥ n, q the number of demand points, and 6 is some positive constant which can be as small as needed. © 2005 IEEE.en_US
dc.languageengen_US
dc.relation.ispartofInternational Conference on Advanced Information Networking and Applications Proceedingsen_US
dc.subjectApproximation Algorithmsen_US
dc.subjectDistributed and Parallel Computingen_US
dc.subjectLocation Problemen_US
dc.subjectMeshen_US
dc.subjectP-Medianen_US
dc.subjectParallel Computersen_US
dc.titleAn approximation solution for the 2-median problem on two-dimensional meshesen_US
dc.typeConference_Paperen_US
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hken_US
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/AINA.2005.92en_US
dc.identifier.scopuseid_2-s2.0-33744480808en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33744480808&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume2en_US
dc.identifier.spage457en_US
dc.identifier.epage460en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridTse, SSH=7006643113en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US
dc.identifier.issnl1550-445X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats