Metraipolis › archive › dc_20431c3d2fef

Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting — arXiv:2609.35386

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35386
License (as archived)
CC0-1.0
Archived
2026-10-07T22:14:07.848Z
SHA-256 of the archived text
dac6b1ded98bff1d192d10cddfbda7b9e7d79bbc5e7591266371d00228670b8c
Stable URL of this page
https://metraipolis.com/documento/dc_20431c3d2fef

How to cite

Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting — arXiv:2609.35386 — arXiv (en), https://arxiv.org/abs/2609.35386 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_20431c3d2fef (Metraipolis archive dc_20431c3d2fef, sha256 dac6b1ded98bff1d192d10cddfbda7b9e7d79bbc5e7591266371d00228670b8c)
BibTeX
@misc{dc20431c3d2fef,
  title = {Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting — arXiv:2609.35386},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35386},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_20431c3d2fef; sha256 dac6b1ded98bff1d192d10cddfbda7b9e7d79bbc5e7591266371d00228670b8c},
  year = {2026}
}

Archived text

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

We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-29 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.35386 — 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-07T21:55:21.850Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).