Metraipolis › archive › dc_fb61e37cf567
Ulam Median is NP-hard for Four Permutations — arXiv:2608.05544
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.05544
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T10:51:06.458Z
- SHA-256 of the archived text
6f7ad8cf5b0ea95844a53252a5dd522081f7626e094025a3652e0e66b4b9c700- Stable URL of this page
https://metraipolis.com/documento/dc_fb61e37cf567
How to cite
Ulam Median is NP-hard for Four Permutations — arXiv:2608.05544 — arXiv (en), https://arxiv.org/abs/2608.05544 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fb61e37cf567 (Metraipolis archive dc_fb61e37cf567, sha256 6f7ad8cf5b0ea95844a53252a5dd522081f7626e094025a3652e0e66b4b9c700)
BibTeX
@misc{dcfb61e37cf567,
title = {Ulam Median is NP-hard for Four Permutations — arXiv:2608.05544},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.05544},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fb61e37cf567; sha256 6f7ad8cf5b0ea95844a53252a5dd522081f7626e094025a3652e0e66b4b9c700},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05544. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty--Das--Krauthgamer, SODA '21). Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-07 in cs.CC). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2608.05544 — 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-31T10:38:22.104Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).