Конусы полистепеней и задачи комбинаторной оптимизации

М. Н. Вялый

?

Конусы полистепеней и задачи комбинаторной оптимизации

Журнал вычислительной математики и математической физики. 2013. Т. 53. № 5. С. 816–824.

Конус полистепеней двойственен конусу неотрицательных многочленов. В данной работе рассматривается связь этого конуса с задачами комбинаторной оптимизации. Для этого используются тензорные расширения многогранников задач комбинаторной оптимизации. Показано, что многогранник задачи MAX-2-CSP (оптимизационная версия задачи 2-выполнимости) тензорной степени 4k совпадает с пересечением конуса 4k-полистепеней с подходящим аффинным пространством. Таким образом, в отличие от SDP-релаксаций, релаксация до конуса полистепеней становится точной уже при расширении степени 4.

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое математика

Язык: русский

Ключевые слова: комбинаторная оптимизация конусы полистепеней тензорные расширения многогранников

Proceedings of the 6th Workshop on Computational Approaches to Discourse, Context and Document-Level Inferences (CODI 2025)

Strube M., Braud C., Hardmeier C. и др., Suzhou: Association for Computational Linguistics, 2025.

Добавлено: 11 июня 2026 г.

On the Ramsey Number R(K_{1,s},P_t)

Kh. Kh. Abdullin, D. B. Mokeev, D. S. Taletskii, Mathematical notes 2026 Vol. 119 No. 1 P. 3–7

Добавлено: 10 июня 2026 г.

TreeDQN: Sample-efficient off-policy reinforcement learning for combinatorial optimization

Sorokin D., Kostin A., Савченко Л. В. и др., Knowledge-Based Systems 2026 Vol. 348 Article 116258

Добавлено: 10 июня 2026 г.

Microbial diversity and production of milk spirit using traditional Buryat fermentation and distillation technologies

Namsaraev Z., Козлова А. Д., Toshchakov S., Scientific Reports 2026 Vol. 16 No. 17769

Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...

Добавлено: 10 июня 2026 г.

Artificial intelligence and digital twins for failure prediction in data center cooling systems: a comprehensive literature review (2018–2026)

Гущин М. И., Butorova A., Bobakov V. и др., European Physical Journal: Special Topics 2026 P. 1–19

Добавлено: 10 июня 2026 г.

Innovations in Information and Decision Sciences. Proceedings of the 13th International Conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA 2025), Volume 4

Springer, 2026.

Добавлено: 8 июня 2026 г.

Wave dynamics within the Whitham-Ostrovsky equation

Flamarion M. V., Пелиновский Е. Н., Nonlinear Dynamics 2026 Vol. 114 Article 784

Добавлено: 5 июня 2026 г.

ML-based Fast Simulation of FARICH Responses

Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.

Добавлено: 19 мая 2026 г.

Bifurcations and Structural Stability of Generic PC-HC Families

Доровский А. А., / Series arXiv "math". 2026.

Добавлено: 14 мая 2026 г.

On the minimum number of maximal distance-k independent sets in trees

Талецкий Д. С., / Series arXiv "math". 2026.

Добавлено: 1 мая 2026 г.

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Овчаренко М. А., / Series arXiv "math". 2026.

Добавлено: 30 апреля 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

Добавлено: 18 апреля 2026 г.

On the dimension of the space of static potentials on three-manifolds

Медведев В. О., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Добавлено: 3 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Колесников А. В., / Series arXiv "math". 2025.

Добавлено: 13 февраля 2026 г.

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.

Эффективное вычисление всех допусков в разреженной задаче о максиминном пути

Каймаков К. В., Малышев Д. С., Успехи математических наук 2024 Т. 79 № 5 С. 185–186

В работе представлен эффективный алгоритм вычисления допусков всех ребер для задачи о максиминном пути, который для разреженных данных улучшает известное достижение Рамасвами, Орлина и Чакраварти. ...

Добавлено: 30 сентября 2024 г.

АЛГОРИТМ ГЕНЕТИЧЕСКОЙ ИНЖЕНЕРИИ (GEA): ЭФФЕКТИВНЫЙ МЕТАЭВРИСТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ

Сохраби М., Фатхоллахи-Фард А. М., Громов В. А., Автоматика и телемеханика 2024 № 3 С. 23–37

Генетические алгоритмы (ГА) известны своей эффективностью в решении задач комбинаторной оптимизации благодаря их способности исследовать разнообразные пространства решений, обрабатывать различные представления, использовать параллелизм, сохранять хорошие решения, адаптироваться к изменяющимся условиям, управлять комбинаторным разнообразием и проводить эвристический поиск. Тем не менее такие ограничения, как преждевременная сходимость, неспецифичность и стохастичность операторов кроссовера и мутации, делают ГА не ...

Добавлено: 8 мая 2024 г.

Exact Algorithm for Generating H-Cores in Simplified Lattice-Based Protein Model

Игнатов А. Д., , in: 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. Communications in Computer and Information Science (CCIS, volume 1913)Vol. 1913.: Springer, 2023. P. 173–187.

Добавлено: 18 января 2024 г.

Competitive Intensity and Quality Maximizing Seedings in Knock-out Tournaments

Дагаев Д. А., Суздальцев А. И., Journal of Combinatorial Optimization 2018 Vol. 35 No. 1 P. 170–188

Добавлено: 1 августа 2017 г.

An enhanced bitstring encoding for exact maximum clique search in sparse graphs

Pablo San Segundo ., Jorge Artieda .., Mikhail Batsyn и др., Optimization Methods and Software 2017 Vol. 32 No. 2 P. 312–335

Добавлено: 9 марта 2017 г.

Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений

Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31

Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...

Добавлено: 20 октября 2016 г.