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).