Optimal cocircuits in regular matroids and applications

Let M = (E, C) be a regular matroid with circuit set H and cocircuit set H and let $\text{(}\text{H}\text{, +, ?)}$ be an ordered group. To given partitions D = D⁺ ∈ D^? for all D ?H and weighting functions ?,k: E → H optimale ê-cocircuits are defined by having a minimal value $\text{K}\text{(}\text{D}{}^{\mathrm{+}}\text{) ? ol(}\text{D}{}^{\mathrm{?}}\text{ø 1^e1}$.It is shown that P as well as NP problems can be formulated by means of optimal cocircuits. We discuss a class of optimal cocircuit problems which can be solved using flow theory in regular matroids. Applications of the derived theory and algorithms to graphic and cographic matroids and to special ordered groups yield polynomial algorithms for some new minimal cut and shortest path problems which are useful in combinatorial and integer optimization problems.