{"id":"arxiv:0805.2646","kind":"preprint","title":"Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems","authors":["Ilias Diakonikolas","Mihalis Yannakakis"],"author_count":2,"year":2008,"published":"2008-05-17","venue":null,"cited_by":null,"doi":null,"arxiv_id":"0805.2646","nct_id":null,"source_url":"https://arxiv.org/abs/0805.2646","archive_url":"https://space-kitty.com/papers/arxiv:0805.2646","updated":"2008-05-17","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/0805.2646","abstract":"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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}