Trioid: A generalization of matroid and the associated polytope

Authors

  • Santosh N. Kabadi
  • Abraham P. Punnen

Abstract

We consider a generalization of the well known greedy algorithm, called m-step greedy algorithm, where m elements are examined in each iteration. When m = 1 or 2, the algorithm reduces to the standard greedy algorithm. For m = 3 we provide a complete characterization of the independence system, called trioid, where the m-step greedy algorithm guarantees an optimal solution for all weight functions. We also characterize the trioid polytope and propose a generalization of submodular functions.

Downloads

How to Cite

Kabadi, S. N., & Punnen, A. P. (2011). Trioid: A generalization of matroid and the associated polytope. Algorithmic Operations Research, 6(1), Pages 29 – 39. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18495

Issue

Vol. 6 No. 1 (2011)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.