Solving Optimization Problems with Diseconomies of Scale

Опубликовано 27 июня 2016, 21:07

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as x q , with the amount x of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is A q , where A q is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for several optimization problems with a diseconomy of scale. Our analysis relies on a decoupling inequality for nonnegative random variables. Consider arbitrary nonnegative jointly distributed random variables Y 1 ,...,Y n . Let X 1 ,...,X n be independent copies of Y 1 ,...,Y n such that all X i are independent and each X i has the same distribution as Y i . Then, E(X 1 +…+X n ) q < C q E(Y 1 +…+Y n ) q . The inequality was proved by de la Pena in 1990. However, the optimal constant C q was not known. We show that the optimal constant is C q =A q . This is a joint work with Maxim Sviridenko, Yahoo Labs.