File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10898-012-9867-6
- Scopus: eid_2-s2.0-84876479099
- WOS: WOS:000316116600009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A linear time approximation scheme for computing geometric maximum k-star
Title | A linear time approximation scheme for computing geometric maximum k-star |
---|---|
Authors | |
Keywords | Approximation Facility dispersion Geometric maximum k-star Linear time approximation scheme |
Issue Date | 2013 |
Citation | Journal of Global Optimization, 2013, v. 55, n. 4, p. 849-855 How to Cite? |
Abstract | Facility dispersion seeks to locate the facilities as far away from each other as possible, which has attracted a multitude of research attention recently due to the pressing need on dispersing facilities in various scenarios. In this paper, as a facility dispersion problem, the geometric maximum k-star problem is considered. Given a set P of n points in the Euclidean plane, a k-star is defined as selecting k points from P and linking k - 1 points to the center point. The maximum k-star problem asks to compute a k-star on P with the maximum total length over its k - 1 edges. A linear time approximation scheme is proposed for this problem. It approximates the maximum k-star within a factor of (1+ ∩) O(n+1/4 log 1)time for any >0. To the best of the authors' knowledge, this work presents the first linear time approximation scheme on the facility dispersion problems. © 2012 Springer Science+Business Media, LLC. |
Persistent Identifier | http://hdl.handle.net/10722/336109 |
ISSN | 2021 Impact Factor: 1.996 2020 SCImago Journal Rankings: 0.861 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, Jia | - |
dc.contributor.author | Hu, Shiyan | - |
dc.date.accessioned | 2024-01-15T08:23:32Z | - |
dc.date.available | 2024-01-15T08:23:32Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Journal of Global Optimization, 2013, v. 55, n. 4, p. 849-855 | - |
dc.identifier.issn | 0925-5001 | - |
dc.identifier.uri | http://hdl.handle.net/10722/336109 | - |
dc.description.abstract | Facility dispersion seeks to locate the facilities as far away from each other as possible, which has attracted a multitude of research attention recently due to the pressing need on dispersing facilities in various scenarios. In this paper, as a facility dispersion problem, the geometric maximum k-star problem is considered. Given a set P of n points in the Euclidean plane, a k-star is defined as selecting k points from P and linking k - 1 points to the center point. The maximum k-star problem asks to compute a k-star on P with the maximum total length over its k - 1 edges. A linear time approximation scheme is proposed for this problem. It approximates the maximum k-star within a factor of (1+ ∩) O(n+1/4 log 1)time for any >0. To the best of the authors' knowledge, this work presents the first linear time approximation scheme on the facility dispersion problems. © 2012 Springer Science+Business Media, LLC. | - |
dc.language | eng | - |
dc.relation.ispartof | Journal of Global Optimization | - |
dc.subject | Approximation | - |
dc.subject | Facility dispersion | - |
dc.subject | Geometric maximum k-star | - |
dc.subject | Linear time approximation scheme | - |
dc.title | A linear time approximation scheme for computing geometric maximum k-star | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s10898-012-9867-6 | - |
dc.identifier.scopus | eid_2-s2.0-84876479099 | - |
dc.identifier.volume | 55 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 849 | - |
dc.identifier.epage | 855 | - |
dc.identifier.eissn | 1573-2916 | - |
dc.identifier.isi | WOS:000316116600009 | - |