Two-phase greedy algorithms for some classes of combinatorial linear programs
Two-phase greedy algorithms for some classes of combinatorial linear programs
复制标题
某些类别的组合线性规划的两阶段贪婪算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Britta Peis
中科院分区：
文献类型：
--
作者：
U. Faigle;Britta Peis
我们提出了针对某些类别的组合堆积的贪婪算法，并涵盖了霍夫曼和施瓦茨晶格多面体的一般形式框架内的问题。我们的算法在第一阶段计算相关双覆盖和打包问题的蒙日解决方案，然后在第二阶段继续为原始问题构建贪婪解决方案。我们展示了在某些子模和超模假设以及单调约束下算法的最优性。对于具有子模约束的超模晶格多面体，我们的算法提供了目前已知的 Edmonds 多拟阵贪婪算法的最广泛的推广。
We present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of Hoffman and Schwartz' lattice polyhedra. Our algorithms compute in a first phase Monge solutions for the associated dual cover and packing problems and then proceed to construct greedy solutions for the primal problems in a second phase. We show optimality of the algorithms under certain sub- and supermodular assumptions and monotone constraints. For supermodular lattice polyhedra with submodular constraints, our algorithms offer the farthest reaching generalization of Edmonds' polymatroid greedy algorithm currently known.