Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

Details Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

2008-05-17

arxiv.org/abs/0805.2646v1

Computer Science

Data Structures and Algorithms

submitted full version

Scientific paper

We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $\epsilon$ the Pareto curve of a multiobjective optimization problem. We show that for a broad class of bi-objective problems (containing many important widely studied problems such as shortest paths, spanning tree, and many others), we can compute in polynomial time an $\epsilon$-Pareto set that contains at most twice as many solutions as the minimum such set. Furthermore we show that the factor of 2 is tight for these problems, i.e., it is NP-hard to do better. We present upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number $k$ of solutions which provide a good approximation to the Pareto curve.

Affiliated with

Also associated with

No associations

Rating

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614078