LIPIcs.ESA.2022.80.pdf
- Filesize: 0.73 MB
- 12 pages
Document
The Pareto Cover Problem
Authors
Bento Natura 
,
Meike Neuwohner ,
Stefan Weltge
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.ESA.2022.80
https://doi.org/10.4230/LIPIcs.ESA.2022.80
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Randomness, geometry and discrete structures
- Theory of computation → Dynamic programming
- Theory of computation → Packing and covering problems
- Theory of computation → Problems, reductions and completeness
- Mathematics of computing → Discrete optimization
Keywords
- Pareto
- Covering
- Optimization
- Approximation Algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer Science & Business Media, 1999. URL: https://doi.org/10.1007/978-3-642-58412-1.
- Michael R Garey and David S Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990. URL: https://dl.acm.org/doi/10.5555/574848.
- James Luedtke, Shabbir Ahmed, and George L Nemhauser. An integer programming approach for linear programs with probabilistic constraints. Mathematical programming, 122(2):247-272, 2010. URL: https://doi.org/10.1007/s10107-008-0247-4.
- Arkadi Nemirovski and Alexander Shapiro. Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17(4):969-996, 2007. URL: https://doi.org/10.1137/050622328.
- Salil P Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing, 31(2):398-427, 2001. URL: https://doi.org/10.1137/S0097539797321602.