- Оценка производительности алгоритмов аппроксимации для задачи двухвершинного сильносвязного подграфа минимального размера(arXiv)
Автор : Аззам Хабиб
Аннотация:Джабери [7] представил алгоритмы аппроксимации для задачи вычисления 2-вершинного сильно двусвязного подграфа минимального размера в ориентированных графах. Мы реализовали алгоритмы аппроксимации, представленные в [7], и протестировали реализацию на некоторых графах. Экспериментальные результаты показывают, что эти алгоритмы хорошо работают на практике.
2.Улучшенные алгоритмы аппроксимации состояния произведения для квантовых локальных гамильтонианов (arXiv)
Автор: Тиаго Бергамаски
Аннотация:Энергия основного состояния и свободная энергия квантовых локальных гамильтонианов являются фундаментальными величинами в квантовой физике многих тел, однако в целом их оценить с помощью QMA-трудно. В этой статье мы разрабатываем новые методы для нахождения классических аддитивных аппроксимаций состояния произведения ошибок для этих величин на некоторых семействах квантовых k-локальных гамильтонианов. А именно, те, которые либо плотны, имеют низкий пороговый ранг, либо определены на разреженном графе, исключающем фиксированный минор, основанные на методах и системах, изученных Брандао и Харроу, Гарибиан и Кемпе, а также Бансалом, Брави и Терхалом. Мы представляем два основных технических вклада. Во-первых, мы обсуждаем связь между аппроксимацией состояния произведения локальных гамильтонианов и проверкой свойств комбинаторного графа. Мы разрабатываем ряд лемм о слабой регулярности Семереди для k-локальных гамильтонианов, основанных на леммах Фриза, Каннана и других. Мы используем их для разработки алгоритмов дискретизации с постоянным временем и для характеристики «сложности вершинной выборки» задачи локального гамильтониана по аналогии с классическим результатом Алона, де ла Веги, Каннана и Карпински. Во-вторых, мы основываемся на теоретико-информационных методах аппроксимации состояния произведения Брандао и Харроу, распространяя их результаты на свободную энергию и на асимметричный граф. Мы используем эту структуру для определения семейств алгоритмов для свободной энергии при низких температурах и новых алгоритмов для определенных семейств разреженных графов.
3.Алгоритмы аппроксимации маршрутов роботов в случайных полях с гарантированной точностью оценки(arXiv)
Автор: Шамак Дутта, Нильс Уайлд, Пратап Токекар, Стивен Л. Смит
Аннотация: мы изучаем задачу о размещении образцов и поиске кратчайшего маршрута для роботов, которым поручено картографировать явления окружающей среды, смоделированные как стационарные случайные поля. Цель состоит в том, чтобы свести к минимуму используемые ресурсы (образцы или продолжительность тура), гарантируя при этом точность оценки. Мы даем приближенные алгоритмы для обеих задач в выпуклых средах. Это улучшает ранее известные результаты как с точки зрения теоретических гарантий, так и с точки зрения моделирования. Кроме того, мы опровергаем существующее в литературе утверждение о нижней оценке решения задачи о размещении выборки.
