Paroids: A canonical format for combinatorial optimization (Q1199464): Difference between revisions

A paroid is a matroid with ground set \(E\) and family of independent sets \(I\), and a partition \(E_ 1,E_ 2,\dots,E_ p\) of \(E\). A paroid independent set is the union of some subsets \(E_ i\) if it belongs to \(I\). The authors consider the problem of finding maximum weight paroid independent sets or bases. If \(| E_ i|=k\) for every \(i\), this reduces to the \(k\)-polymatroid matching problem which includes \(k\)- matroid intersection and matching. However, it also includes travelling salesman, vertex packing, satisfiability, graph partitioning and knapsack. The authors develop a structural hierarchy of paroids as well as duals and minors, and then briefly review their other paper about a generic paroid search algorithm.