Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions:
(1) super-modular functions
(2) proper functions
(3) uncrossable function
All of which is covered in his PhD thesis titled: "On the design of approximation algorithms for a class of graph problems.", 1993.
My question is that where is the difficulty coming when we move from 0-1 proper to uncrossable functions?? May be some example would also help. Is there some variant of uncrossable function which is superset of proper functions in general?? Also, why do we not consider sub-modular functions?? Why types of problems would have sub-modular functions. (i know about the trivial example of modular function i.e. cut $\delta(S)$ but nothing much). So where is difficulty coming when we consider sub-modular functions or are they too easy?? This would probably let me know the inspiration to consider the super-modular functions. Also a related question is that sometimes we replace two crossable sets by uncrossing sets, like when we construct the tree corresponding to laminarity concept. Is this always possible?? (in case of every supermodular function?? or only in uncrossable functions??) Interesting references would also help.
