Approximation Limits of Linear Programs (Beyond Hierarchies)
Approximation Limits of Linear Programs (Beyond Hierarchies)
We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove …