论文标题
贪婪算法在跳跃系统和三角洲的优化问题的地球属性
Geodesic Property of Greedy Algorithms for Optimization Problems on Jump Systems and Delta-matroids
论文作者
论文摘要
Bouchet和Cunningham（1995）引入的跳跃系统的概念是满足某个交换属性的整数点。我们考虑跳跃系统上可分开的凸功能的最小化。众所周知，该问题可以通过贪婪的算法解决。在本文中，我们对贪婪算法是否具有地理特性感兴趣，这意味着该算法生成的溶液的轨迹是从初始溶液到最近的最佳溶液的测量线。我们表明，贪婪算法的特殊实现享有地球属性，而原始算法则却没有。作为推论，我们提出了一种新的贪婪算法，用于在三角洲 - 摩托病上进行线性优化，并表明该算法具有地理特性。
The concept of jump system, introduced by Bouchet and Cunningham (1995), is a set of integer points satisfying a certain exchange property. We consider the minimization of a separable convex function on a jump system. It is known that the problem can be solved by a greedy algorithm. In this paper, we are interested in whether the greedy algorithm has the geodesic property, which means that the trajectory of solution generated by the algorithm is a geodesic from the initial solution to a nearest optimal solution. We show that a special implementation of the greedy algorithm enjoys the geodesic property, while the original algorithm does not. As a corollary to this, we present a new greedy algorithm for linear optimization on a delta-matroid and show that the algorithm has the geodesic property.
