A linear algorithm for integer programming in the plane. (English) Zbl 1079.90581
Summary: We show that a 2-variable integer program, defined by \(m\) constraints involving coefficients with at most \(\varphi\) bits, can be solved with \(O(m+\varphi)\) arithmetic operations on rational numbers of size \(O(\varphi)\).
MSC:
| 90C10 | Integer programming |
Keywords:
integer programReferences:
| [1] | Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Reading: Addison-Wesley, 1974 · Zbl 0326.68005 |
| [2] | Banaszczyk, W., Litvak, A.E., Pajor, A., Szarek, S.J.: The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Math. Oper. Res. 24 (3), 728-750 (1999) · Zbl 0965.52009 · doi:10.1287/moor.24.3.728 |
| [3] | Barvinok, A.: A course in convexity. vol. 54 of Graduate Studies in Mathematics. Providence, RI: Am. Math. Soc. 2002 · Zbl 1014.52001 |
| [4] | Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. Assoc. Comput. Mach. 42, 488-499 (1995) · Zbl 0885.65063 |
| [5] | Eisenbrand, F.: Fast integer programming in fixed dimension. In: Proceedings of the 11th Annual European Symposium on Algorithms, ESA? 2003, G.D. Battista, U. Zwick (eds.), vol. 2832 of LNCS, Springer, 2003. To appear in Computing · Zbl 1266.90130 |
| [6] | Eisenbrand, F., Rote, G.: Fast 2-variable integer programming. In: Integer Programming and Combinatorial Optimization, IPCO 2001, K. Aardal, B. Gerards (eds.), vol. 2081 of LNCS, Springer, 2001, pp. 78-89 · Zbl 1010.90048 |
| [7] | Eisenbrand, F.: Short vectors of planar lattices via continued fractions. Inf. Proc. Lett. 79 (3), 121-126 (2001) · Zbl 1032.68138 · doi:10.1016/S0020-0190(00)00186-1 |
| [8] | Feit, S.D.: A fast algorithm for the two-variable integer programming problem. J. Assoc. Comput. Mach. 31 (1), 99-113 (1984) · Zbl 0642.90075 |
| [9] | Gauß, C.F.: Disquisitiones arithmeticae. Gerh. Fleischer Iun., 1801 |
| [10] | Hirschberg D.S., Wong, C.K.: A polynomial algorithm for the knapsack problem in two variables. J. Assoc. Comput. Mach. 23 (1), 147-154 (1976) · Zbl 0345.90048 |
| [11] | Kanamaru, N., Nishizeki, T., Asano, T.: Efficient enumeration of grid points in a convex polygon and its application to integer programming. Inter. J. Comput. Geo. Appl. 4 (1), 69-85 (1994) · Zbl 0807.90086 · doi:10.1142/S0218195994000069 |
| [12] | Kannan R., Lovász, L.: Covering minima and lattice-point-free convex bodies. An. Math. 128, 577-602 (1988) · Zbl 0659.52004 · doi:10.2307/1971436 |
| [13] | Kannan, R.: A polynomial algorithm for the two-variable integer programming problem. J. Assoc. Comp. Mach. 27 (1), 118-122 (1980) · Zbl 0423.90052 |
| [14] | Khintchine, A.Y.: Continued Fractions. Noordhoff, Groningen, 1963 · Zbl 0117.28503 |
| [15] | Knuth, D.: The art of computer programming. vol. 2. Addison-Wesley, 1969 · Zbl 0191.18001 |
| [16] | Lagarias, J.C.: Worst-case complexity bounds for algorithms in the theory of integral quadratic forms. J. Algor. 1, 142-186 (1980) · Zbl 0473.68030 · doi:10.1016/0196-6774(80)90021-8 |
| [17] | Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8 (4), 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538 |
| [18] | Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. Assoc. Comp. Mach. 31, 114-127 (1984) · Zbl 0637.90064 |
| [19] | Scarf, H.E.: Production sets with indivisibilities. Part I: generalities. Econometrica 49, 1-32 (1981) · Zbl 0446.90006 |
| [20] | Scarf, H.E.: Production sets with indivisibilities. Part II: The case of two activities. Econometrica 49, 395-423 (1981) · Zbl 0458.90008 |
| [21] | Schönhage, A.: Fast reduction and composition of binary quadratic forms. In: Inter. Symp. Symb. Alg. Comp. ISSAC 91, ACM Press, 1991, pp. 128-133 · Zbl 1019.11505 |
| [22] | Schrijver, A.: Theory of Linear and Integer Programming. John Wiley, 1986 · Zbl 0665.90063 |
| [23] | Zamanskij, L.Y., Cherkasskij, V.D.: A formula for determining the number of integral points on a straight line and its application. Ehkon. Mat. Metody (in Russian). 20, 1132-1138 (1984) · Zbl 0569.90060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
