Csaba, Béla and Thomas, Plick and Ali, Shokoufandeh (2013) Optimal random matchings, tours, and spanning trees in hierarchically separated trees. THEORETICAL COMPUTER SCIENCE, 500. pp. 68-89. ISSN 0304-3975
|
Text
1307.6939v1.pdf Available under License Creative Commons Attribution. Download (313kB) | Preview |
Official URL: https://doi.org/10.1016/j.tcs.2013.05.021
Abstract
We derive tight bounds on the expected weights of several combinatorial optimization problems for random point sets of size n distributed among the leaves of a balanced hierarchically separated tree. We consider monochromatic and bichromatic versions of the minimum matching, minimum spanning tree, and traveling salesman problems. We also present tight concentration results for the monochromatic problems. © 2013 Elsevier B.V.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Metric space; Hierarchically separated tree; Euclidean optimization; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 25 Jun 2024 13:49 |
| Last Modified: | 25 Jun 2024 13:49 |
| URI: | https://real.mtak.hu/id/eprint/198684 |
Actions (login required)
 |
Edit Item |
