Статья
Min-Cost Multiflows in Node-Capacitated Undirected Networks
Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток называется допустимым, если сумма весов $T$-путей, проходящих через каждую вершину $v$, не превышает $c(v)$. Величиной $F$ называется сумма весов $F(P)$, а стоимостью $F$ называется сумма (по всем $T$-путям $P$) произведений $F(P)$ на стоимости путей $P$ относительно функции $a$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.
В статье представлена специализированная структура данных, предназначенная для хранения и выполнения различных операций с графами социальных сетей больших объемов. Предложенная структура хранения ориентирована на поддержку операций пополнения и выгрузки подграфов и поиска кратчайших путей между двумя группами вершин.
Пусть задан орграф $G = (VG,AG)$. Четным фактором $M \subseteq AG$ называется множество ребер, образованное набором вершинно непересекающихся путей и четных циклов. Четные факторы были введены Гиленом и Каннингхемом, они обобщают т.н. path matchings в неориентированных графах. Задача нахождения четного фактора максимального размера в графе общего вида является NP-трудной, однако для класса нечетно циклически симметричных орграфов эта задача является полиномиальной. К настоящему моменту был известен лишь один комбинаторный способ ее решения, принадлежащий Папу. Этот алгоритм имеет сложность $O(n^4)$ (где $n$ обозначает число вершин в $G$, а $m$ обозначает число ребер). В данной работе мы развиваем новую технику разреженного восстановления и строим алгоритм со сложностью $O(n^3 \log n)$, находящий нечетный фактор максимального размера в нечетно циклически симметричном орграфе. Наш подход также применим к другим аналогичным задачам, например к задаче нахождения максимального простого $b$-паросочетания без квадратов.
Сборник составлен по результатам исследований молодых ученых, аспирантов и студентов МЭСИ, а также ряда вузов Москвы, Йошкар-Олы, Магнитогорска, Махачкалы, Пензы, Саранска, Саратова, Улан-Удэ. Рассмотренные на конференции (июнь 2011 г.) результаты исследований посвящены вопросам статистической методологии, применению математико-статистических и эконометрических методов в различных отраслях экономики и социальной сфере. Обобщается зарубежный опыт статистического анализа ряда проблем экономической и социальной жизни. Сравнивается эффективность различных методов, формулируются рекомендации по их выбору в зависимости от специфики решаемой задачи.
В основе настоящего учебного пособия лежит специальный курс по выбору студента, прочитанный автором на механико - математическом факультете МГУ им. М.В. Ломоносова в 2010-2012 учебных годах. Пособие знакомит читателя с методом параметрикса и его дискретным аналогом, развитым в самое последнее время автором пособия и его коллегами-соавторами. Оно объединяет воедино материал, который ранее содержался только в ряде журнальных статей. Не стремясь к максимальной общности изложения, автор ставил целью продемонстрировать возможности метода при доказательстве локальных предельных теорем о сходимости марковских цепей к диффузионному процессу и при получении двусторонних оценок типа Аронсона для некоторых вырожденных диффузий.
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.