Small (Explicit) Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
TalkinFrenchat Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) · 2017-11-06..11-09
summary
The talk presents an explicit small extended formulation for knapsack cover inequalities by connecting them to monotone Boolean circuit constructions. It explains how monotone circuits can be used to derive compact linear-programming extensions that capture knapsack cover constraints, giving a concrete construction and size bounds for the formulation.
AI-written summary · about