On the complexity of integer programming
From MaRDI portal
Publication:3922169
DOI10.1145/322276.322287zbMath0468.68050OpenAlexW2103658959MaRDI QIDQ3922169
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322276.322287
Related Items
Length-bounded disjoint paths in planar graphs, Hyperplane separation technique for multidimensional mean-payoff games, Minimal resolutions of lattice ideals and integer linear programming, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Complexity and Polynomially Solvable Special Cases of QUBO, The Complexity of Reversal-Bounded Model-Checking, Non-E-Overlapping, Weakly Shallow, and Non-Collapsing TRSs are Confluent, Numerical semigroups generated by quadratic sequences, The width and integer optimization on simplices with bounded minors of the constraint matrices, Fast and efficient bit-level precision tuning, Novel geometric approach for virtual coiling, Complexity of modal logics with Presburger constraints, The two‐variable fragment with counting and equivalence, A theoretical framework for cardinality-based feature models: the semantics and computational aspects, Deciding Boolean algebra with Presburger arithmetic, Approximation algorithms for Hamming clustering problems, Testing additive integrality gaps, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Reasoning with Global Assumptions in Arithmetic Modal Logics, Integer programming in parameterized complexity: five miniatures, An expanding-core algorithm for the exact \(0-1\) knapsack problem, New techniques for linear arithmetic: cubes and equalities, Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy, Using linear constraints for logic program termination analysis, A new probabilistic constraint logic programming language based on a generalised distribution semantics, Block-structured integer programming: can we parameterize without the largest coefficient?, Fast and succinct population protocols for Presburger arithmetic, On the complexity of achieving proportional representation, Complexity of optimizing over the integers, On the optimality of pseudo-polynomial algorithms for integer programming, Presburger Büchi tree automata with applications to logics with expressive counting, Unnamed Item, Solving Nonlinear Integer Arithmetic with MCSAT, Linear Arithmetic with Stars, A logic for preference lifting under uncertainty and its decidability, The master equality polyhedron with multiple rows, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, Polyhedral geometry and combinatorics of an autocatalytic ecosystem, Trichotomy for integer linear systems based on their sign patterns, Binary decision rules for multistage adaptive mixed-integer optimization, Knapsack in graph groups, Machines Over the Reals and Non-Uniformity, Combinatorial \(n\)-fold integer programming and applications, An Analysis of Slow Convergence in Interval Propagation, The Distributions of Functions Related to Parametric Integer Optimization, An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable, Computational Complexity of Atomic Chemical Reaction Networks, An appraisal of computational complexity for operations researchers, How to Block Blood Flow by Using Elastic Coil, On the Identity Problem for the Special Linear Group and the Heisenberg Group., Faster Algorithms for Integer Programs with Block Structure, Finding cut-offs in leaderless rendez-vous protocols is easy, Trichotomy for the reconfiguration problem of integer linear systems, Integer Programming in Parameterized Complexity: Three Miniatures., On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, Constants and finite unary relations in qualitative constraint reasoning, The complexity landscape of decompositional parameters for ILP, On the path-width of integer linear programming, Automata for unordered trees, Target counting with Presburger constraints and its application in sensor networks, Mixed-integer quadratic programming is in NP, Partitioned EDF scheduling on a few types of unrelated multiprocessors, A note on non-degenerate integer programs with small sub-determinants, The complexity of finite model reasoning in description logics, Vectors in a box, Unnamed Item, Preprocessing composite cutting procedure: an approach to the integer model, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Decision Procedures for Multisets with Cardinality Constraints, Coalgebraic Hybrid Logic, Abelian Networks I. Foundations and Examples, Stable divisorial gonality is in NP, On the integrality gap of binary integer programs with Gaussian data, On the integrality gap of binary integer programs with Gaussian data, Fast Cube Tests for LIA Constraint Solving, A complete and terminating approach to linear integer solving, On Integer Programming and Convolution., Unnamed Item, \(\mathbb N\)-solutions to linear systems over \(\mathbb Z\), Detectability of labeled weighted automata over monoids, Complexity of the two-variable fragment with counting quantifiers, THE LOGIC OF COMPARATIVE CARDINALITY, A genetic algorithm of determining cycle time for printed circuit board assembly lines, Decidable integration graphs., On the Complexity of Inverse Mixed Integer Linear Optimization, The complexity of the satisfiability problem for Krom formulas, Constructing NP-intermediate problems by blowing holes with parameters of various properties, A Sharp Bound for Solutions of Linear Diophantine Equations, The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions, Cutting to the chase., An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
