Metraipolis › archive › dc_dfe1aa218ce6

Optimal Non-Adaptive Vantage Point Selection — arXiv:2609.10267

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.10267
License (as archived)
CC0-1.0
Archived
2026-10-16T11:17:58.850Z
SHA-256 of the archived text
7a79ae6ea9625b4b8a059c20cbb62b47e753f81c4e064dc68047a5f4f35a38e2
Stable URL of this page
https://metraipolis.com/documento/dc_dfe1aa218ce6

How to cite

Optimal Non-Adaptive Vantage Point Selection — arXiv:2609.10267 — arXiv (en), https://arxiv.org/abs/2609.10267 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dfe1aa218ce6 (Metraipolis archive dc_dfe1aa218ce6, sha256 7a79ae6ea9625b4b8a059c20cbb62b47e753f81c4e064dc68047a5f4f35a38e2)
BibTeX
@misc{dcdfe1aa218ce6,
  title = {Optimal Non-Adaptive Vantage Point Selection — arXiv:2609.10267},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.10267},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dfe1aa218ce6; sha256 7a79ae6ea9625b4b8a059c20cbb62b47e753f81c4e064dc68047a5f4f35a38e2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10267. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tilde{\Omega}(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tilde{\Theta}(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $\alpha k$ queries for $\alpha\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tilde{\Theta}\left( \min\left\{ \frac{n}{\alpha k}, \max\left( \sqrt{\frac{n}{\alpha}}, \frac{n^{2/3}}{\alpha k^{1/3}} \right) \right\} \right). $$

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.10267 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T10:56:12.724Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).