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