Title: Applications of Relaxed Submodularity
Combinatorial optimization problems often give rise to set-functions which satisfy the sub- or supermodular inequality only for certain pairs of subsets. Here we discuss connectivity problems and show how results on relaxed submodular functions help in solving them.
1991 Mathematics Subject Classification: 90C27, 05C40
Keywords and Phrases: combinatorial optimization, submodular functions, connectivity of graphs
Full text: dvi.gz 23 k, dvi 52 k, ps.gz 71 k.
Home Page of DOCUMENTA MATHEMATICA