Content deleted Content added
m →Example: +. |
m Remove unneeded grammatical article from short description and general fixes |
||
Line 1:
{{Short description|
An '''integer programming''' problem is a [[mathematical optimization]] or [[Constraint satisfaction problem|feasibility]] program in which some or all of the variables are restricted to be [[integer]]s. In many settings the term refers to '''integer [[linear programming]]''' (ILP), in which the [[objective function]] and the constraints (other than the integer constraints) are [[Linear function (calculus)|linear]].
Line 159:
* Kannan<ref>{{Cite journal|last=Kannan|first=Ravi|date=1987-08-01|title=Minkowski's Convex Body Theorem and Integer Programming|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415|journal=Mathematics of Operations Research|volume=12|issue=3|pages=415–440|doi=10.1287/moor.12.3.415|s2cid=495512 |issn=0364-765X}}</ref> presented an improved algorithm with run-time <math>n^{O(n)}\cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Goemans|first1=Michel X.|author1link = Michel Goemans|last2=Rothvoss|first2=Thomas|date=2020-11-07|title=Polynomiality for Bin Packing with a Constant Number of Item Types|journal=[[Journal of the ACM]]|volume=67|issue=6|pages=38:1–38:21|doi=10.1145/3421750|hdl=1721.1/92865 |s2cid=227154747 |issn=0004-5411|doi-access=free|hdl-access=free}}</ref>
* Frank and Tardos<ref>{{Cite journal|last1=Frank|first1=András|last2=Tardos|first2=Éva|date=1987-03-01|title=An application of simultaneous diophantine approximation in combinatorial optimization|url=https://doi.org/10.1007/BF02579200|journal=Combinatorica|language=en|volume=7|issue=1|pages=49–65|doi=10.1007/BF02579200|s2cid=45585308|issn=1439-6912}}</ref> presented an improved algorithm with run-time <math>n^{2.5 n} \cdot 2^{O(n)} \cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Bliem|first1=Bernhard|last2=Bredereck|first2=Robert|last3=Niedermeier|first3=Rolf|author3-link=Rolf Niedermeier|date=2016-07-09|title=Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels|url=https://dl.acm.org/doi/abs/10.5555/3060621.3060636|journal=Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence|series=IJCAI'16|___location=New York, New York, USA|publisher=AAAI Press|pages=102–108|isbn=978-1-57735-770-4}}</ref><ref>{{Cite book|last1=Bredereck|first1=Robert|last2=Kaczmarczyk|first2=Andrzej|last3=Knop|first3=Dušan|last4=Niedermeier|first4=Rolf|title=Proceedings of the 2019 ACM Conference on Economics and Computation |chapter=High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming |date=2019-06-17|chapter-url=https://doi.org/10.1145/3328526.3329649|series=EC '19|___location=Phoenix, AZ, USA|publisher=Association for Computing Machinery|pages=505–523|doi=10.1145/3328526.3329649|isbn=978-1-4503-6792-9|s2cid=195298520}}</ref>{{Rp|Prop.8}}
* Dadush<ref>Dadush, Daniel (2012-06-14). [https://homepages.cwi.nl/~dadush/papers/dadush-thesis.pdf "Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation].</ref> presented an improved algorithm with run-time <math>n^n \cdot 2^{O(n)} \cdot (m \cdot \log V)^{O(1)}</math>.
* Reis and Rothvoss<ref>Reis, Victor; Rothvoss, Thomas (2023-03-26). [https://arxiv.org/abs/2303.14605 "The Subspace Flatness Conjecture and Faster Integer Programming"].
▲* Reis and Rothvoss<ref>Reis, Victor; Rothvoss, Thomas (2023-03-26). [https://arxiv.org/abs/2303.14605 "The Subspace Flatness Conjecture and Faster Integer Programming"]. </ref> presented an improved algorithm with run-time <math>(\log n)^{O(n)} \cdot (m\cdot \log V)^{O(1)}</math>.
These algorithms can also be used for '''mixed integer linear programs''' (MILP) - programs in which some variables are integer and some variables are real.<ref name=":1">{{Cite web |last=Hildebrand |first=Robert |date=2016-10-07 |title=FPT algorithm for mixed integer program |url=https://cstheory.stackexchange.com/a/36738/9453 |access-date=2024-05-21 |website=Theoretical Computer Science Stack Exchange |language=en}}</ref> The original algorithm of Lenstra<ref name=":0" />{{Rp|___location=Sec.5}} has run-time <math>2^{O(n^3)}\cdot poly(d,L)</math>, where n is the number of integer variables, d is the number of continuous variables, and ''L'' is the binary encoding size of the problem. Using techniques from later algorithms, the factor <math>2^{O(n^3)}</math> can be improved to <math>2^{O(n\log n)}</math> or to <math>n^n</math>.<ref name=":1" />
| |||