В этой заметке я собираюсь поделиться своим пониманием/экспозицией статьи Tight Bounds for Approximate Carathéodory and Beyond [1], написанной Mirrokni et al. Эта заметка в основном состоит из 2 частей: в первой половине мы используем простую мотивационную задачу для иллюстрации алгоритма, предложенного Mirrokni et al. Во второй половине мы изучаем ключевые этапы их доказательства для оценки предложенного алгоритма. В конце даются краткие комментарии об интересных идеях в статье...