Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке $[0,1]$

Одномерная задача кластеризации $k$-medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка $[0,1]$. Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных $n$ и $k$ строится верхняя оценка $0.5n/(2k-1)$ нижней цены игры. Обосновывается достижимость найденной оценки при $k>1$ и достаточно больших $n=n(k)$. Тем самым показывается, что для произвольной выборки длины $n$ может быть построена кластеризация методом $k$ медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач.