Algorithms for standard-form ILP problems via Komlós’ discrepancy setting

?

Algorithms for standard-form ILP problems via Komlós’ discrepancy setting

Ch. 388. P. 25:1–25:22.

Gribanov D., Khayaleyev T., Cherniavskii M., Klimenko M., Malyshev D., Moiseev S.

We study the standard-form ILP problem max{c⊤x:Ax=b,x∈Zn≥0}, where A∈Zk×n has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k×k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κk denote the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. Up to polynomial factors in the input size, the optimization problem can be solved in time O(κk)2kΔ2, and the corresponding feasibility problem in time O(κk)kΔ. Using the best currently known bound κk=O˜(log1/4k), this yields running times O(logk)k2(1+o(1))Δ2 and O(logk)k4(1+o(1))Δ, respectively. Under the Komlós conjecture, the dependence on k in both running times reduces to 2O(k).

Publication based on the results of:

Network and graph models, algorithmic complexity and data mining (2025)

In book

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, Pardalos P. M. et al., Computational Optimization and Applications 2025 Vol. 92 P. 811–861

In this paper, we consider the counting function $\QEnum(y) = |\PC_{y} \cap \ZZ^{n_x}|$ for a parametric polyhedron $\PC_{y} = \{ x \in \RR^{n_x} \colon A x \leq b + B y\}$, where $y \in \RR^{n_y}$. We give a new representation of $\QEnum(y)$, called a \emph{piece-wise step-polynomial with periodic coefficients}, which is a generalization of piece-wise ...

Added: December 6, 2024

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

Gribanov D., Malyshev D., Shumilov I., Operations Research Forum 2024 Vol. 5 Article 32

In our note, we present a very simple and short proof of a new interesting fact about the faces of an integer hull of a given rational polyhedron. This fact has a complete analog in linear programming theory and can be useful to establish new constructive upper bounds on the number of vertices in an integer hull of ...

Added: April 4, 2024

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

Gribanov D., Shumilov I., Malyshev D. et al., 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 ...

Added: March 6, 2024

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

Gribanov D., Malyshev D., Siberian Electronic Mathematical Reports 2022 Vol. 19 No. 2 P. 613–626

Let a polytope P be defined by a system Ax ≤ b. We consider the problem to count a number of integer points inside P, assuming that P is ∆-modular. The polytope P is ∆-modular if all the rank sub-determinants of A are bounded by ∆ in the absolute value. We present a new FPT-algorithm, ...

Added: September 19, 2022

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

Gribanov D., Shumilov I., Dmitry Malyshev et al., Journal of Global Optimization 2024 Vol. 88 P. 591–651

Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $\max\{c^\top x \colon A x = b,\, x \in \ZZ^n_{\geq 0}\}$, where all the entries of $A,b,c$ are integer, parameterized by the number of rows of $A$ and $\|A\|_{\max}$. This class of problems is known under ...

Added: May 10, 2022

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

Belogaev A., Alexey Elokhin, Krasilov A. et al., IEEE Access 2020 Vol. 8 P. 169010–169023

Intelligent Transportation Systems (ITS) will become an essential part of every city in the near future. They should support various vehicle-to-everything (V2X) applications that improve road safety or even enable autonomous driving. Recently, the European Telecommunications Standards Institute (ETSI) introduced a multi-access (mobile) edge computing concept as a promising solution to satisfy the V2X delay ...

Added: September 18, 2020

On Happy Colorings, Cuts, and Structural Parameterizations

Bliznets I., 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.

We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always ...

Added: November 1, 2019

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

Bliznets I., Springer, 2019.

Added: October 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.

Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model generally clusters are defined as cliques. However, such approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different ...

Added: October 30, 2018

Subexponential Parameterized Algorithm for Interval Completion

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

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most kedge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan et al. [FOCS 1994; ...

Added: October 30, 2018

Parameterized Complexity of Superstring Problems

Bliznets Ivan, Fomin F., Golovach P. et al., Algorithmica 2017 Vol. 79 No. 3 P. 798–813

In the Shortest Superstring problem we are given a set of strings S=\{s_1, \ldots , s_n\} and integer \ell and the question is to decide whether there is a superstring s of length at most \ellcontaining all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2^{\mathcal {O}(k)} {\text {poly}}(n) finds a ...

Added: October 29, 2018

Computability and Complexity

Day A., Fellows M., Greenberg N. et al., Berlin: Springer, 2017.

Added: October 26, 2018

A Mathematical Model for the Astronaut Training Scheduling Problem

Musatova E. G., Lazarev A. A., Ponomarev K. et al., 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 ...

Added: October 31, 2016

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

Belenky A., 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 ...

Added: October 21, 2016

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

Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31

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

Added: October 20, 2016

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

Lazarev A. A., Musatova E. G., Управление большими системами: сборник трудов 2012 № 38 С. 161–169

We consider the problem of cars-to-train assignments, routing and scheduling, which is to minimize the weighted average time of transportation orders execution by consistently choosing the compound of trains, their routes from origins to destinations, and schedules. We offer the new integer problem settings to account for different cases of practical constraints. ...

Added: November 23, 2012