UC Berkeley

Integer programming formulations play a key role in the design of efficient algorithms and approximation algorithms for many discrete linear optimization problems as found in previous research. A specific integer programming formulation of a discrete linear optimization problem may lead to algorithms with better running time or approximation algorithms with better approximation factors than the other algorithms for the same problem. Inspired by this, we introduce here new integer programming formulations to devise efficient algorithms and approximation algorithms for two classes of problems, the covariate balancing problems and the Replenishment Storage problems.The existence of certain special integer programming formulations is an evidence of the existence of polynomial time algorithms for some discrete optimization problems. For a variant of the covariate balancing problems, our new integer programming formulation has a network structure that was not previously known. We use this new formulation to devise network flow algorithms, which have better running time than an existing polynomial time algorithm. Other integer programming formulations we introduce show that several variants of the class of covariate balancing problems are fixed-parameter tractable. Integer programming formulations are often important in designing approximation algorithms for intractable problems. The Replenishment Storage problems were known to be NP-hard and one approximation algorithm was known for a special variant of the class. We derive for this variant a polynomial time approximation scheme using a new integer programming formulation. Our new formulation also leads to the first known approximation scheme for another variant of this class. Moreover, this resolves the complexity status of some variants of the Replenishment Storage problems as weakly NP-hard.