Есть и другие показатели качества: Дхамдхер и др. Изучают «среднее» искажение:
Тем не менее, интересующая меня мера - это та, которая используется MDS-подобными методами, которая смотрит на среднюю аддитивную ошибку:
Хотя MDS-подобные методы широко изучаются за пределами сообщества теории CS, мне известна только одна статья ( Dhamdhere и др. ), В которой рассматривается оптимизация под эту меру, и это тоже для ограниченной задачи встраивания в линию ( ) (примечание: дипломная работа Тасоса Сидиропулоса 2005 года MS имеет хороший обзор предыдущих работ)
Есть ли какие-либо более поздние работы, о которых люди знают о строгом анализе качества под этим понятием ошибки? В то время как эти проблемы, как правило, NP-сложные, меня больше интересуют приближения любого рода.
источник
Я могу что-то упустить, но почему ? Мы заинтересованы в аддитивном приближении, поэтому мы не можем масштабировать, чтобы сделать для всех , верно?ϵ2≤(ρ−1)∑d(x,y)2 f(μ(x),μ(y))≥d(x,y) x,y
Одним из преимуществ здесь является то, что мы можем делать плохо на коротких отрезках и в конечном итоге быть в порядке. Кроме того, является ли проблема легкой (даже приблизительной), если, скажем, мы хотим встроить в ? (Можем ли мы написать математическую программу, чтобы захватить вопрос?)ℓ2
источник