Computer Science/Discrete Mathematics Seminar I

In this talk, we will sketch the theory of simultaneous optimization for concave profit functions, and point out connections to fairness. More precisely, suppose we would like to simultaneously approximate all symmetric utility functions over a convex feasiblity region. We characterize the optimum simultaneous approximation, and present polynomial time algorithms for obtaining this optimum. We prove that our solution is a logarithmic approximation simultaneously for all symmetric utility functions. Here, a utility function is assumed to be concave, zero at zero, and non-decreasing in each argument. This problem is equivalent to doing approximately fair resource allocation under all a priori reasonable measures of fairness. We will illustrate this approach for the problem of bandwidth allocation in networks. In particular, we will show how this allocation can be obtained using a distributed primal-dual algorithm very similar in spirit to TCP with per-flow information. If time permits, we will also illustrate this approach in the context of machine scheduling. Joint work with Meyerson and Cho.