Polynomial-Time Aggregation of Integer Programming Problems

DOI10.1145/322358.322368MaRDI QIDQ3657783zbMATH OpenOpenAlexFDO

Authors R. Kannan

Publication date 1983

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322358.322368

zbMATH Keywords

aggregation of linear Diophantine equationsknapsack problemNP-completenesspolynomial-time algorithm

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Integer programming (90C10)

Cited in

(12)

• A new enumeration scheme for the knapsack problem
• On the hardness of approximating shortest integer relations among rational numbers
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Zero duality gap in surrogate constraint optimization: a concise review of models
• Optimal constraints aggregation method for ILP
• Aggregating assignment constraints
• Integer Farkas lemma
• Space-efficient algorithm for integer programming with few constraints
• On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints
• A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems
• Using aggregation to optimize long-term production planning at an underground mine
• An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))

This page was built for publication: Polynomial-Time Aggregation of Integer Programming Problems

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