Algorithms for Standard-form ILP Problems via Komlós’ Discrepancy Setting

Публикации

?

Algorithms for Standard-form ILP Problems via Komlós’ Discrepancy Setting

Грибанов Д. В., Khayaleyev T., Cherniavskii M., Klimenko M., Малышев Д. С., Moiseev S.

Язык: английский

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Сетевые и графовые модели, сложность алгоритмов и интеллектуальный анализ данных (2025)

В книге

ESA'2026: Proceedings of the 34th Annual European Symposium on Algorithms

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2026.

A new and faster representation for counting integer points in parametric polyhedra

Dmitry V. Gribanov, Dmitry S. Malyshev, Пардалос П. О. и др., Computational Optimization and Applications 2025 Vol. 92 P. 811–861

Добавлено: 6 декабря 2024 г.

On a simple connection between Δ-modular ILP and LP, and a new bound on the number of integer vertices

Грибанов Д. В., Малышев Д. С., Shumilov I., Operations Research Forum 2024 Vol. 5 Article 32

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

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

Грибанов Д. В., Shumilov I., Малышев Д. С. и др., Journal of Global Optimization 2024 Vol. 89 P. 1033–1067

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Zn , assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = b, x ≥ 0 with a sparse ...

Добавлено: 6 марта 2024 г.

A faster algorithm for counting the integer points number in ∆-modular polyhedra

Грибанов Д. В., Малышев Д. С., Siberian Electronic Mathematical Reports 2022 Vol. 19 No. 2 P. 613–626

Добавлено: 19 сентября 2022 г.

On Delta-modular integer linear problems in the canonical form and equivalent problems

Грибанов Д. В., Shumilov I., Dmitry Malyshev и др., Journal of Global Optimization 2024 Vol. 88 P. 591–651

Добавлено: 10 мая 2022 г.

Cost-Effective V2X Task Offloading in MEC-assisted Intelligent Transportation Systems

Белогаев А. А., Alexey Elokhin, Красилов А. Н. и др., IEEE Access 2020 Vol. 8 P. 169010–169023

Добавлено: 18 сентября 2020 г.

On Happy Colorings, Cuts, and Structural Parameterizations

Близнец И. А., Sagunov D., , in: Graph-Theoretic Concepts in Computer Science 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised PapersVol. 11789: Lecture Notes in Computer Science.: Springer, 2019. P. 148–161.

Добавлено: 1 ноября 2019 г.

Graph-Theoretic Concepts in Computer Science 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers

Близнец И. А., Springer, 2019.

Добавлено: 29 октября 2019 г.

Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

Bliznets Ivan, Karpov N., , in: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).: [б.и.], 2017. P. 6:1–6:14.

Добавлено: 30 октября 2018 г.

Subexponential Parameterized Algorithm for Interval Completion

Bliznets Ivan, Fomin F., Pilipczuk M. и др., ACM Transactions on Algorithms 2018 Vol. 14 No. 3 P. 1–62

Добавлено: 30 октября 2018 г.

Parameterized Complexity of Superstring Problems

Bliznets Ivan, Fomin F., Golovach P. и др., Algorithmica 2017 Vol. 79 No. 3 P. 798–813

Добавлено: 29 октября 2018 г.

Computability and Complexity

Day A., Fellows M., Greenberg N. и др., Berlin: Springer, 2017.

Добавлено: 26 октября 2018 г.

A Mathematical Model for the Astronaut Training Scheduling Problem

Мусатова Е. Г., Лазарев А. А., Ponomarev K. и др., IFAC-PapersOnLine 2016 Vol. 49 No. 12 P. 221–225

We consider a problem of the astronaut training scheduling. Each astronaut has his own set of tasks which should be performed with respect to resource and time constraints. The problem is to determine start moments for all considered tasks. For this issue a mathematical model based on integer linear programming is proposed. Computational results of ...

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

Calculating the minimal fraction of thepopular vote to win the U.S. Presidency in the electoral college

Беленький А. С., Computers & Mathematics with Applications 2005 Vol. 50 No. 5-6 P. 783–802

As is known, in U.S. presidential elections, all 50 states and the District of Columbi(DC) award their electoral votes to (the electors of) U.S. presidential candidates based on the popular vote received by (the electors of) the candidates there (although two different schemes of awarding the electoral votes are currently applied in the U.S.). For ...

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

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

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

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

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

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

Лазарев А. А., Мусатова Е. Г., Управление большими системами: сборник трудов 2012 № 38 С. 161–169

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

Добавлено: 23 ноября 2012 г.