Optima of dual integer linear programs

DOI10.1007/BF02122549MaRDI QIDQ1105488zbMATH OpenOpenAlexWikidataFDO

Authors Ron Aharoni, Nathan Linial, P. Erdős

Publication date 1988

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02122549

zbMATH Keywords

packingcovering integer linear programspair of linear programs

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Metric aspects of integer linear programming
• Approximation of optima of integer programs of the packing—covering type
• Metric relations in integer-valued linear programming
• scientific article; zbMATH DE number 4204114
• Classes of linear programs with integral optimal solutions

Cites work

• Approximation algorithms for combinatorial problems
• Decomposition of regular matroids
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximum degree and fractional matchings in uniform hypergraphs
• On the ratio of optimal integral and fractional covers

Cited in

(14)

• The support of integer optimal solutions
• New class of 0-1 integer programs with tight approximation via linear relaxations
• scientific article; zbMATH DE number 3904332 (Why is no real title available?)
• Metric relations in integer-valued linear programming
• Linear programming bounds for codes via a covering argument
• scientific article; zbMATH DE number 2159271 (Why is no real title available?)
• Improved parallel approximation of a class of integer programming problems
• Combinatorial problems of packing and covering and related problems of integer linear program\-ming
• Classes of linear programs with integral optimal solutions
• The maximum clique problem
• On the relationship between the optima of linear and integer linear programming
• scientific article; zbMATH DE number 5257230 (Why is no real title available?)
• Metric aspects of integer linear programming
• scientific article; zbMATH DE number 4020843 (Why is no real title available?)

This page was built for publication: Optima of dual integer linear programs

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