?
Algorithms for standard-form ILP problems via Komlós’ discrepancy setting
Ch. 388. P. 25:1–25:22.
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).
Keywords: integer linear programmingparameterized complexityFPT algorithmsKomlós’ conjectureDiscrepancy
Publication based on the results of:
In book
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2026.
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
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
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
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
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
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
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
Bliznets I., Springer, 2019.
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: October 29, 2019
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
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
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
Day A., Fellows M., Greenberg N. et al., Berlin: Springer, 2017.
Added: October 26, 2018
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
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