DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.80

The Pareto Cover Problem

Authors: Bento Natura, Meike Neuwohner, and Stefan Weltge

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

We introduce the problem of finding a set B of k points in [0,1]ⁿ such that the expected cost of the cheapest point in B that dominates a random point from [0,1]ⁿ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for k = 2 when each coordinate is drawn from {0,1}, and obtain an FPTAS for general fixed k under mild assumptions on the distributions.

Cite as

Bento Natura, Meike Neuwohner, and Stefan Weltge. The Pareto Cover Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 80:1-80:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{natura_et_al:LIPIcs.ESA.2022.80,
  author =	{Natura, Bento and Neuwohner, Meike and Weltge, Stefan},
  title =	{{The Pareto Cover Problem}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{80:1--80:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.80},
  URN =		{urn:nbn:de:0030-drops-170186},
  doi =		{10.4230/LIPIcs.ESA.2022.80},
  annote =	{Keywords: Pareto, Covering, Optimization, Approximation Algorithm}
}

Search Results

Documents authored by Weltge, Stefan

The Pareto Cover Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message