A linear algorithm for integer programming in the plane

DOI10.1007/s10107-004-0520-0zbMath1079.90581OpenAlexW2033597899MaRDI QIDQ1771307

Sören Laue, Friedrich Eisenbrand

Publication date: 19 April 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/121635

zbMATH Keywords

integer program

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items

Lifting for the integer knapsack cover polyhedron ⋮ Convex minization over \(\mathbb Z^2\) ⋮ Computing efficiently the lattice width in any dimension ⋮ On minimum integer representations of weighted games ⋮ Split Cuts in the Plane ⋮ On the exact separation of mixed integer knapsack cuts ⋮ Unbounded knapsack problems with arithmetic weight sequences ⋮ Integer programming with 2-variable equations and 1-variable inequalities ⋮ Logahedra: A New Weakly Relational Domain ⋮ Efficient Lattice Width Computation in Arbitrary Dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering minima and lattice-point-free convex bodies
• Short vectors of planar lattices via continued fractions
• Integer Programming with a Fixed Number of Variables
• Linear Programming in Linear Time When the Dimension Is Fixed
• A Fast Algorithm for the Two-Variable Integer Programming Problem
• A Polynomial Algorithm for the Two-Variable Integer Programming Problem
• Production Sets with Indivisibilities, Part I: Generalities
• Production Sets with Indivisibilities, Part II: The Case of Two Activities
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
• A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
• EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING
• Las Vegas algorithms for linear and integer programming when the dimension is small
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• Algorithms - ESA 2003