- Докажите, что GHA 1.5-приближенный для случая строк длины не больше трех.
- Найдите как можно более точную оценку снизу на приближение GHA на строках длины не больше трех.
- Докажите жадную гипотезу для строк длины не больше трех, пользуясь тем, что суммарный оверлэп жадного решения не более чем в два раза меньше суммарного оверлэпа оптимального решения.
- Попробуйте доказать используемое утверждение.
- Докажите какую-нибудь жадную гипотезу для случая строк, каждая из которых состоит из различных символов. В алгоритме обвала мы можем обвалить вершину, если после ее обвала решение остается связным, при этом в “промежуточном состоянии”, когда мы уже отцепили пару ребер сверху, но еще не прицепили снизу, решение может быть несвязным.
- Рассмотрим вариант алгоритма обвала, который прям совсем не нарушает связность: во время прохода по очередному уровню все пары ребер вида (pref(v), v), (v, suff(v)) мы сначала заменяем на ребра вида (pref(v), suff(v)) (они формально не лежат в иерархическом графе), пока это не нарушает связность, и когда мы закончили обрабатывать весь уровень, все “промежуточные” ребра мы заменяем на (pref(v), suff(pref(v))), (pref(suff(v)), suff(v)). Связаны ли как-нибудь жадные иерархические гипотезы для исходного обвала и для этого обвала? Может быть что-то из чего-то следует? Попробуйте доказать жадную гипотезу с новым обвалом для каких-нибудь частных случаев.
- https://docs.google.com/presentation/d/1ahgFjTvJlGvZ5Ci3_2tB5Mvtln9M_Hwm/edit?usp=sharing&ouid=101100644011427327597&rtpof=true&sd=true
- Ответ везде нет (6cnt.cpp):
- Правда ли, что в алгоритме MGREEDY можно так выбрать вершины в циклах минимального покрытия (будем считать, что можно выбрать любую вершину цикла в иерархическом графе, не обязательно исходную), что полученное решение будет содержать GHA?
- Тот же вопрос, но с концовкой “что полученное решение можно обвалить в GHA?”
- Можно заметить, что любое локальное различие правил (т.е. MGREADY, TGREADY, GHA, или какой-либо ещё алгоритм на основе композиции определённых правило выбора, из кого выпустить на текущем слое) могут различаться (и причём очень сильно).
- Верно ли, что если GHA alpha-приближенный для случая примитивных строк, то и любой жадный алгоритм alpha-приближенный?
- На самом деле вообще мы можем так поменять строки, что любой жадный выбор с отношением к OPT, больше alpha станет единственным, а отношение всё ещё будет больше alpha.
- Придумайте какие-нибудь классы решений, не содержащие GHA, которые обваливаются в GHA после удвоения.
- Единственный такой класс пока - это содержащие GHA. И поскольку CSC не верно (не любое решение, удвоив мы обвалим в GHA), то нам вообще ничего не гарантирует, что ещё такие классы есть.
- Докажите что нибудь про гипотезу: пусть D это эйлерово решение, в котором из любой исходной вершины выходит по крайней мере две пары ребер, и пусть D_i это результат работы CA(D) после обработки уровней выше i. Тогда для любой вершины v с уровня i или ниже существуют пути eps -> v и v -> eps, которые не проходят по вершинам выше уровня i.
- Это очевидно, неверно, так как из этого бы следовала неверная CSC гипотеза.
- Докажите, что из жадной иерархической гипотезы следует равномерная 2-приближенность GHA.
- Жадная иерархическая гипотеза эквивалентна CSC (в силу 8), а следовательно не верна, и любые следствия из неё доказывать бессмысленно.
- Улучшите оценки снизу и сверху во всех ячейках таблицы в readme.md. Желательно до состояния равных в пределе отношений.
- Поймите, что происходит с компрессией.
- Для обычного GA она <=2OPT.
- Если нужен цикл, то <=3OPT.
- А что с примитивными строками?
- А что с побуквенной компрессией?
- GHA <= OPT + OPTCC?
- В произвольных модулях вершин и весх (не обяз. оверлэпы). Но верно нер-во Монжа и |a|>=w(a,b). Правда ли, что строятся циклы так же?
- Првада ли, что покрытия для подмножества не хуже, чем для всего множества. Очевидно, не правда:
4---->4---->4 ^ | | | | v 4 4 ^ | | | | v 4----->4--->4 И выбираем диагональ. Для неё покрытие 8, а для исходного графа 0. - Ограниченный по длине строки.
- Например, GA для <=4, и GHA для <=5.