Solving Optimization Problems with Diseconomies of Scale

179 views · Published 27 June 2016 · 57:48 · Indexed 23 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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.

More from this channel