论文标题
帕累托封面问题
The Pareto cover problem
论文作者
论文摘要
我们介绍了一个问题的问题，即在$ [0,1]^n $中找到$ k $的$ b $点，以使$ b $中最便宜点的预期成本从$ [0,1]^n $中占主导地位。我们研究了随机点的坐标是独立分布并且成本函数是线性的。此问题自然出现在各种应用领域，这些应用程序基于预定义的产品满足客户的要求，每种都对应于一部分功能。我们表明，当每个坐标从$ \ {0,1 \} $绘制时，问题已经为$ k = 2 $，并且在分布中的温和假设下获得了一般固定$ k $的fptas。
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.
