An extreme point theorem for ordered polymatroids on chain orders

MaRDI QIDQ1380702zbMATH OpenFDO

Authors Ulrich Krüger

Publication date 12 March 1998

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119436, http://www.emis.de/journals/SLC/wpapers/s36krueger.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extreme point characterizationgreedy algorithmordered polymatroids

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Review text

We consider ordered polymatroids as a generalization of polymatroids and extend the extreme point characterization of polymatroids by the greedy algorithm to the ordered case. It is proved that a feasible point of an ordered polymatroid is a vertex iff it is a greedy-vector with respect to an appropriate primal greedy-procedure.

Recommendations

• The Partial Order of a Polymatroid Extreme Point
• Structural aspects of ordered polymatroids
• scientific article; zbMATH DE number 3904604
• Adjacency on polymatroids

Cited in

(5)

• Structural aspects of ordered polymatroids
• Adjacency on polymatroids
• The Partial Order of a Polymatroid Extreme Point
• scientific article; zbMATH DE number 1187952 (Why is no real title available?)
• The numbers of edges of the order polytope and the chain polytope of a finite partially ordered set

This page was built for publication: An extreme point theorem for ordered polymatroids on chain orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380702)