Content deleted Content added
→See also: Diophantine equations also have integer solutions. |
fix broken ref |
||
Line 178:
== Sparse integer programming ==
It is often the case that the matrix <math>A</math> that defines the integer program is ''[[Sparse matrix|sparse]]''. In particular, this occurs when the matrix has a [[Block matrix|block structure]], which is the case in many applications. The sparsity of the matrix can be measured as follows. The ''graph'' of <math>A</math> has vertices corresponding to columns of <math>A</math>, and two columns form an edge if <math>A</math> has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The ''sparsity measure'' <math>d</math> of <math>A</math> is the minimum of the [[tree-depth]] of the graph of <math>A</math> and the [[tree-depth]] of the graph of the transpose of <math>A</math>. Let <math>a</math> be the ''numeric measure'' of <math>A</math> defined as the maximum absolute value of any entry of <math>A</math>. Let <math>n</math> be the number of variables of the integer program. Then it was shown in 2018<ref>{{
| last1 = Koutecký | first1 = Martin
| last2 = Levin | first2 = Asaf
| last3 = Onn | first3 = Shmuel
| editor1-last = Chatzigiannakis | editor1-first = Ioannis
| editor2-last = Kaklamanis | editor2-first = Christos
| editor3-last = Marx | editor3-first = Dániel
| editor4-last = Sannella | editor4-first = Donald
| arxiv = 1802.05859
| contribution = A parameterized strongly polynomial algorithm for block structured integer programs
| doi = 10.4230/LIPICS.ICALP.2018.85
| pages = 85:1–85:14
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic
| volume = 107
| year = 2018}}</ref> that integer programming can be solved in [[strongly polynomial]] and [[fixed-parameter tractable]] time parameterized by <math>a</math> and <math>d</math>. That is, for some computable function <math>f</math> and some constant <math>k</math>, integer programming can be solved in time <math>f(a,d)n^k</math>. In particular, the time is independent of the right-hand side <math>b</math> and objective function <math>c</math>. Moreover, in contrast to the classical result of Lenstra, where the number <math>n</math> of variables is a parameter, here the number <math>n</math> of variables is a variable part of the input.
==See also==
| |||