It is commonly accepted that matroids provide an abstract setting for which greedy optimization works (although there are more general structures known as 'greedoids').

I was wondering whether there had been attempts to formalize a notion of 'semi-greediness'. Intuitively, it means that we would still construct a solution iteratively, but going from a solution $S$ of cost $i$ to a solution $S'$ of cost $i+1$ would work differently: instead of having $S'$ of the form $S \cup \{x\}$, we could for example have $S'$ of the form $(S \Delta T) \cup \{x\}$ i.e. we would replace $r$ elements present in $S$ by $r+1$ elements exterior to $S$.

This could possibly model interesting problems such as bipartite maximum matching, optimizations in $\Delta$-matroids or 2-polymatroids.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.