Properties of the d-dimensional earth mover's problem
Properties of the d-dimensional earth mover's problem
复制标题
d 维推土机问题的性质
DOI：
10.1016/j.dam.2019.02.042
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jeffery Kline
中科院分区：
文献类型：
--
作者：
Jeffery Kline
D维推土机问题目标函数的最优值可以看作是定义在归一化有限多集XϕR+n上的实值泛函⊂.我们证明了ϕ具有许多有用的性质：它是齐次的，平移不变的，它具有形式为⊂的单调性ϕX≤ϕY蕴含着ϕXϕY和ϕ是ϕ可加的，即ϕX+Y=ϕX+ϕY.我们还证明了对于容许X，可以使用单阶段贪婪算法同时生成定义ϕ的原始和对偶线性规划的解，并且对偶的解反映X的几何形状。
The optimal value of the objective function of the d-dimensional earth mover’s problem can be viewed as a real-valued functional ϕ that is defined on normalized and finite multisets X⊂ R+ n. We show that ϕ possesses a variety of useful properties: it is homogeneous, translation invariant, it has a monotonicity property of the form conv X⊂ conv Y implies ϕ X≤ ϕ Y and ϕ is Minkowski additive, ie, ϕ X+ Y= ϕ X+ ϕ Y. We also show that for admissible X, solutions to the primal and dual linear programs that define ϕ may be generated simultaneously using a single-phase greedy algorithm and that solutions to the dual reflect the geometry of X.
影响因子：
19.5
作者：
Rubner, Y;Tomasi, C;Guibas, LJ
通讯作者：
Guibas, LJ