Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
| dc.creator | Diakonikolas, Ilias | |
| dc.creator | Yannakakis, Mihalis | |
| dc.date | 2008-05-17 | |
| dc.date.accessioned | 2026-07-07T09:39:35Z | |
| dc.date.available | 2026-07-07T09:39:35Z | |
| dc.description | We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $ε$ 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 $ε$-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. | |
| dc.description | submitted full version | |
| dc.identifier | https://arxiv.org/abs/0805.2646 | |
| dc.identifier | http://arxiv.org/abs/0805.2646 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161225 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems | |
| dc.type | text |