Timezone: »

Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
Alan Kuhnle · J. Smith · Victoria Crawford · My T. Thai

Thu Jul 12 09:15 AM -- 12:00 PM (PDT) @ Hall B #145

The optimization of submodular functions on the integer lattice has received much attention recently, but the objective functions of many applications are non-submodular. We provide two approximation algorithms for maximizing a non-submodular function on the integer lattice subject to a cardinality constraint; these are the first algorithms for this purpose that have polynomial query complexity. We propose a general framework for influence maximization on the integer lattice that generalizes prior works on this topic, and we demonstrate the efficiency of our algorithms in this context.

Author Information

Alan Kuhnle (University of Florida)
J. Smith (University of Florida)
Victoria Crawford (University of Florida)
My T. Thai (University of Florida)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors