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

CREATORDiptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit, Aravinda Kanchana Ruwanpathirana
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE174 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10050

Browse the full library · About the Tower of Babel