Optimization Online


Trioid: A generalization of matroid and the associated polytope

Santosh Kabadi(kabadi***at***unb.ca)
Abraham Punnen(apunnen***at***sfu.ca)

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.

Keywords: matroid, trioid, submodular functions

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Manuscript, Department of Mathematics, Simnon Fraser University Surrey, 2009

Download: [PDF]

Entry Submitted: 08/10/2009
Entry Accepted: 08/11/2009
Entry Last Modified: 08/10/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society