A linear algorithm for integer programming in the plane

DOI10.1007/S10107-004-0520-0MaRDI QIDQ1771307zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Algorithms and Computation
• scientific article; zbMATH DE number 1757949
• Integer programming with 2-variable equations and 1-variable inequalities
• A Fast Algorithm for the Two-Variable Integer Programming Problem
• Lower time bounds for integer programming with two variables

Cites work

• scientific article; zbMATH DE number 3910134 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1273650 (Why is no real title available?)
• scientific article; zbMATH DE number 1757949 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 3191379 (Why is no real title available?)
• A Fast Algorithm for the Two-Variable Integer Programming Problem
• A Polynomial Algorithm for the Two-Variable Integer Programming Problem
• A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
• Covering minima and lattice-point-free convex bodies
• EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING
• Fast integer programming in fixed dimension
• Integer Programming with a Fixed Number of Variables
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Linear Programming in Linear Time When the Dimension Is Fixed
• Production Sets with Indivisibilities, Part I: Generalities
• Production Sets with Indivisibilities, Part II: The Case of Two Activities
• Short vectors of planar lattices via continued fractions
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

Cited in

(19)

• Lifting for the integer knapsack cover polyhedron
• Unbounded knapsack problems with arithmetic weight sequences
• EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING
• Integer programming with 2-variable equations and 1-variable inequalities
• A Heuristic Ceiling Point Algorithm for General Integer Linear Programming
• Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
• A fast algorithm for unbounded monotone integer linear systems with two variables per inequality via graph decomposition
• On minimum integer representations of weighted games
• Lower time bounds for integer programming with two variables
• Convex minization over \(\mathbb Z^2\)
• Split cuts in the plane
• On the exact separation of mixed integer knapsack cuts
• Computing efficiently the lattice width in any dimension
• A Fast Algorithm for the Two-Variable Integer Programming Problem
• Logahedra: a new weakly relational domain
• Efficient lattice width computation in arbitrary dimension
• Polynomial time certifying algorithms for the planar quantified integer programming problem
• On the path-width of integer linear programming
• Integer quadratic programming in the plane

This page was built for publication: A linear algorithm for integer programming in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1771307)