Journal article
Optimal random matchings, tours, and spanning trees in hierarchically separated trees
Theoretical computer science, v 500
19 Aug 2013
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.
Metrics
5 Record Views
Details
- Title
- Optimal random matchings, tours, and spanning trees in hierarchically separated trees
- Creators
- Béla Csaba - Western Kentucky UniversityThomas A. Plick - Drexel UniversityAli Shokoufandeh - Drexel University
- Publication Details
- Theoretical computer science, v 500
- Publisher
- Elsevier
- Grant note
- ONRN000140410363 / IIS Division and Office of Naval Research 0803670 / National Science Foundation
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000323872400005
- Scopus ID
- 2-s2.0-84881475701
- Other Identifier
- 991019169707704721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods