[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SERIES:

Tuesday, October 7, 2014
3:00 pm
Ryerson 251

Konstantin Makarychev
Microsoft Research
Reaearch.microsoft.com/en/people/komakary

Abstract: “Solving Optimization Problems with Diseconomies of Scale”



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^(1/q).
 This is a joint work with Maxim Sviridenko, Yahoo Research–New York.

Joint Host: Professor Razborov and Toyota Technological Institute at Chicago
*Refreshments will be served prior to the talk in Ryerson 255 at 2:30 pm*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141007/f358ae45/attachment.htm