CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Randomized vs. deterministic distance query strategies for point location on the line

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Discrete Applied Mathematics (0166-218X). Vol. 154 (2006), 3, p. 478-484.
[Artikel, refereegranskad vetenskaplig]

Suppose that n points are located at n mutually distinct but unknown positions on the line, and we can measure their pairwise distances. How many measurements are needed to determine their relative positions uniquely? The problem is motivated by DNA mapping techniques based on pairwise distance measures. It is also interesting for its own and surprisingly deep. Continuing our earlier work on this problem, we give a simple randomized two-round strategy that needs, with high probability, only (1+o(1))n measurements. We show that deterministic strategies cannot manage the task in two rounds with (1+o(1))n measurements in the worst case. We improve an earlier deterministic bound to roughly 4n/3 measurements.

Nyckelord: learning by queries, randomized strategy, graph rigidity, DNA mapping

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 17897