کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421092 684132 2015 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the generality of the greedy algorithm for solving matroid base problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the generality of the greedy algorithm for solving matroid base problems
چکیده انگلیسی

It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or kk-sum objective functions.In this paper, we address matroid base problems with a more general–“universal”–objective function which contains the previous ones as special cases. This universal objective function is of the sum type and associates multiplicative weights with the ordered cost coefficients of the elements of matroid bases such that, by choosing appropriate weights, many different–classical and new–objectives can be modeled. We show that the greedy algorithm is applicable to a larger class of objective functions than commonly known and, as such, it solves universal matroid base problems with non-negative or non-positive weight coefficients. Based on problems with mixed weights and a single (−,+)(−,+)-sign change in the universal weight vector, we give a characterization of uniform matroids. In case of multiple sign changes, we use partition matroids. For non-uniform matroids, single sign change problems can be reduced to problems in minors obtained by deletion and contraction. Finally, we discuss how special instances of universal bipartite matching and shortest path problems can be tackled by applying greedy algorithms to associated transversal matroids.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 195, 20 November 2015, Pages 114–128
نویسندگان
, , ,