Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or unbounded below?
Fact 1: For monotone submodular functions, Nemhauser, Wolsey and Fisher proved [1] that simple greedy algorithm gives $1-1/e$ approximation guarantee.
Fact 2: For non-monotone non-negative submodular functions, Buchbinder et. all proved [2] that randomized greedy algorithm gives $1/e$ approximation for cardinality constraint.