Maximizing Diversity in (near-)Median String Selection
Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, Aravinda Kanchana Ruwanpathirana · 2026
Read Maximizing Diversity in (near-)Median String Selection by Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, Aravinda Kanchana Ruwanpathirana (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10050.txt.
Description
Picking one consensus string that sits closest to a whole set is a classic aggregation problem. A 2026 paper led by Diptarka Chakraborty, with three co-authors, asks for more: several near-optimal medians that are also diverse, giving decision makers flexibility and robustness. The study works with Hamming distance, where distance counts positions that differ.
The authors first give an exact algorithm for the diameter variant, finding pairs of near-optimal medians as far apart as possible. They then offer an approximation algorithm for sum dispersion and a bi-criteria approximation for the harder min dispersion case, producing more than two diverse medians. Structural insights into median space and code-construction techniques drive the results.
Catalog record
| CREATOR | Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, Aravinda Kanchana Ruwanpathirana |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 174 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-10050