Sequential Facility Location: Approximate Submodularity and Greedy Algorithm

We develop and analyze a novel utility function and a fast optimization algorithm for subset selection in sequential data that incorporates the underlying dynamic model of data. We propose a capacitated sequential facility location function that finds a fixed number of representatives that well encode the data, where the sequence of representatives are compatible with the dynamic model of data. As maximizing this new objective function is NP-hard, we develop a fast greedy algorithm based on submodular maximization. Unlike the conventional facility location, the computation of the marginal gain in our case cannot be done by operations on each item independently. We exploiting the sequential structure of the problem and develop an efficient dynamic programming-based algorithm that exactly computes the marginal gain. We investigate conditions on the dynamic transition model of data, under which our utility function is submodular or $\epsilon$-approximately submodualr, hence, the greedy algorithm comes with performance guarantees. By experiments on synthetic data and the real-world problem of procedure learning from instructional videos, we show that our framework not only significantly improves the computational time, but also achieves better objective function values and obtains more coherent summaries.