In multiobjective optimization, solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in a class of solutions that capture the trade-off between these objectives, the so-called Pareto curve. Unfortunately, the Pareto curve is, in general, of exponential size. It can be shown that, under very general conditions, there is a polynomially succinct curve that approximates the Pareto curve arbitrarily closely. We give a necessary and sufficient condition under which this approximate Pareto curve can be constructed in polynomial in the size of the instance and the desired approximation. 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 findings 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. (which was actually the original motivation for this work).