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

Preprint · Ilias Diakonikolas, Mihalis Yannakakis

- Archive id: arxiv:0805.2646
- Published: 2008-05-17
- arXiv: https://arxiv.org/abs/0805.2646
- Source URL: https://arxiv.org/abs/0805.2646
- PDF: https://arxiv.org/pdf/0805.2646
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.