@inproceedings{6e565310910340b59735dc52d1c8af60,
title = "The Pareto Cover Problem",
abstract = "We introduce the problem of finding a set B of k points in [0, 1]n such that the expected cost of the cheapest point in B that dominates a random point from [0, 1]n 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.",
keywords = "Approximation Algorithm, Covering, Optimization, Pareto",
author = "Bento Natura and Meike Neuwohner and Stefan Weltge",
note = "Publisher Copyright: {\textcopyright} 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 30th Annual European Symposium on Algorithms, ESA 2022 ; Conference date: 05-09-2022 Through 09-09-2022",
year = "2022",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.ESA.2022.80",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman",
booktitle = "30th Annual European Symposium on Algorithms, ESA 2022",
}