Metraipolis › archive › dc_0eaa435728ec
On Extensions of the Unanimous Vote Problem — arXiv:2609.36508
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36508
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T19:18:59.571Z
- SHA-256 of the archived text
29e6f9debf21701d31e5af1d7e88cdc5627f1249dc1594900672cb76fc54768d- Stable URL of this page
https://metraipolis.com/documento/dc_0eaa435728ec
How to cite
On Extensions of the Unanimous Vote Problem — arXiv:2609.36508 — arXiv (en), https://arxiv.org/abs/2609.36508 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0eaa435728ec (Metraipolis archive dc_0eaa435728ec, sha256 29e6f9debf21701d31e5af1d7e88cdc5627f1249dc1594900672cb76fc54768d)
BibTeX
@misc{dc0eaa435728ec,
title = {On Extensions of the Unanimous Vote Problem — arXiv:2609.36508},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36508},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0eaa435728ec; sha256 29e6f9debf21701d31e5af1d7e88cdc5627f1249dc1594900672cb76fc54768d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36508. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Unanimous Vote problem is to determine a fixed order in which to flip each of $n$ biased coins, where each coin can be flipped only once, such that the expected number of flips until seeing both a head and a tail (or flipping all coins) is minimized. Duman Keles et al. ( arXiv:2510.16678 [cs.DS]) gave an $\mathcal{O}(n \log n)$-time algorithm for this problem. Extensions of the Unanimous Vote problem are a rich source of stochastic optimization problems. We focus on three: (1) a variant in which each coin can be flipped arbitrarily many times (a solution is thus an infinite sequence of coin choices), (2) a generalization with $d$-sided dice, that can each be rolled once, where dice must be rolled until two different outcomes are observed (or all dice have been rolled), and (3) a different generalization with $d$-sided dice, where dice must be rolled until all $d$ outcomes have been observed. For (1), we show that there is an optimal sequence which follows a simple greedy rule; the same rule only gives a 1-additive approximation for the original problem ( arXiv:2510.16678 [cs.DS]). The rule also yields a correspondence between a particular optimal sequence and a related mechanical word, which we exploit to characterize the conditions under which this optimal sequence is periodic. We establish tight multiplicative and additive adaptivity gaps for this variant. For (2), we show that two different generalizations of the greedy rule from ( arXiv:2510.16678 [cs.DS]) can be combined to obtain a PTAS. For (3), we give an $\mathcal{O}(\log d)$-approximation algorithm by reducing the problem to Submodular Ranking ( arXiv:1007.2503 [cs.DS]); the same reduction technique can be used to yield approximation algorithms for other stochastic probing problems. Finally, we pose a number of related open questions.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.36508 — 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-07T18:45:07.076Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).