Coauthors: Nikhil Bansal, Erik Saule, and Denis Trystram

To achieve the highest performance of modern computer systems, we usually need to solve combinatorial optimizations problem using complex functions that combine different quantities. Each quantity is often easy to optimize by itself but when put together to express a complex actual application, the classical optimization techniques fail to deliver an efficient solution. In this work we present a generic method to optimize monotonic objective functions by approximating the Pareto set of the multi-objective problem where each parameter is an objective function. Essentially, the method enumerates the frontier of best compromise solutions between these quantities and select the solution that brings the best value for the function to optimize. Such approach would be exponential in the general case. However, we show how classical tools from the approximation theory help to address the problem in both theoretical and practical perspective. We present our technique on a multi-user scheduling problem by optimizing the fairness among users.