Integer Programming with a Fixed Number of Variables
From MaRDI portal
Publication:3037135
DOI10.1287/moor.8.4.538zbMath0524.90067WikidataQ29040555 ScholiaQ29040555MaRDI QIDQ3037135
Publication date: 1983
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.8.4.538
polynomial algorithm; integer linear programming; geometry of numbers; basis reduction algorithm; NP- completeness; fixed number of variables
68Q25: Analysis of algorithms and problem complexity
90C10: Integer programming
90C05: Linear programming
Related Items
Block Reduced Lattice Bases and Successive Minima, A natural lattice basis problem with applications, Unit-time scheduling problems with time dependent resources, Fine covers of a VAS language, Quantifier elimination for modules with scalar variables, On integer points in polyhedra, Pinwheel scheduling with two distinct numbers, The context-freeness of the languages associated with vector addition systems is decidable, Lattice translates of a polytope and the Frobenius problem, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, Simultaneous reduction of a lattice basis and its reciprocal basis, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Complexity of scheduling multiprocessor tasks with prespecified processors allocations, Factorization properties of lattices over the integers, Complexity of Presburger arithmetic with fixed quantifier dimension, A polynomial-time approximation scheme for maximizing the minimum machine completion time, Real data-integer solution problems within the Blum-Shub-Smale computational model, On variations of the subset sum problem, An approximation scheme for strip packing of rectangles with bounded dimensions, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, On the limits of nonapproximability of lattice problems, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Cutting-plane proofs in polynomial space, Shop scheduling problems with multiprocessor tasks on dedicated processors, Executing join queries in an uncertain distributed environment, Proportionate progress: A notion of fairness in resource allocation, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables, Approximability of scheduling with fixed jobs, An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling, Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, Discretely ordered modules as a first-order extension of the cutting planes proof system
