Robust Sequence Networked Submodular Maximization
This addresses robust optimization in networked submodular settings, which is incremental as it adapts existing methods to a new scenario with dependencies on sequence and network structure.
The paper tackles the Robust Sequence Networked Submodular Maximization (RoseNets) problem by designing a robust greedy algorithm that is resilient to element removal, with an approximation ratio dependent on removal count and network topology, and demonstrates effectiveness in recommendation and link prediction applications.
In this paper, we study the \underline{R}obust \underline{o}ptimization for \underline{se}quence \underline{Net}worked \underline{s}ubmodular maximization (RoseNets) problem. We interweave the robust optimization with the sequence networked submodular maximization. The elements are connected by a directed acyclic graph and the objective function is not submodular on the elements but on the edges in the graph. Under such networked submodular scenario, the impact of removing an element from a sequence depends both on its position in the sequence and in the network. This makes the existing robust algorithms inapplicable. In this paper, we take the first step to study the RoseNets problem. We design a robust greedy algorithm, which is robust against the removal of an arbitrary subset of the selected elements. The approximation ratio of the algorithm depends both on the number of the removed elements and the network topology. We further conduct experiments on real applications of recommendation and link prediction. The experimental results demonstrate the effectiveness of the proposed algorithm.