On the Approximability of Trade-offs and Optimal Access of Web Sources (Extended Abstract) .
Christos H. Papadimitriou, Mihalis Yannakakis · 2000
We study problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the trade-off between these objectives (the so-called Pareto curve). We point out that, under very general conditions, there is a polynomially succinct curve that -approximates the Pareto curve, for any > 0. We give a necessary and sucient condition under which this approximate Pareto curve can be constructed in time polynomial in the size of the instance and 1=. In the case of multiple linear objectives, we distinguish between two cases: When the underlying feasible region is convex, then we show that approximating the multi-objective problem is equivalent to approximating the single-objective problem. If, however, the feasible region is discrete, then we point out that the question reduces to an old and recurrent one: How does the complexity of a combinatorial optimization problem change when its feasible region is intresected with a hyperplane with small coefficients; we report some interesting new ndings in this domain. Finally, we apply these concepts and techniques to formulate and solve approximately a cost-time-quality trade-off for optimizing access to the world-wide web, in a model first studied by Etzioni et al [EHJ+] (which was actually the original motivation for this work).