Sequence submodular maximization meets streaming
- PDF / 365,097 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 199 Views
Sequence submodular maximization meets streaming Ruiqi Yang1,2 · Dachuan Xu1 · Longkun Guo3
· Dongmei Zhang4
Accepted: 14 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study the problem of maximizing a sequence submodular function in the streaming setting, where the utility function is defined on sequences instead of sets of elements. We encode the sequence submodular maximization with a weighted digraph, in which the weight of a vertex reveals the utility value in selecting a single element and the weight of an edge reveals the additional profit with respect to a certain selection sequence. The edges are visited in a streaming fashion and the aim is to sieve a sequence of at most k elements from the stream, such that the utility is maximized. In this work, we present an edge-based threshold procedure, which makes one pass over the stream, attains an approximation ratio of (1/(2Δ + 1) − O()), consumes O(kΔ/) memory source in total and O(log(kΔ)/) update time per edge, where Δ is the minimum of the maximal outdegree and indegree of the directed graph.
A preliminary version of this paper appeared in Proceedings of the 13th International Conference on Combinatorial Optimization and Applications (COCOA), 2019, pp. 565-575.
B
Longkun Guo [email protected] Ruiqi Yang [email protected] Dachuan Xu [email protected] Dongmei Zhang [email protected]
1
Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, People’s Republic of China
2
School of Mathematical Sciences, University of Chinese Academy Sciences, Beijing 100049, People’s Republic of China
3
Shandong Key Laboratory of Computer Networks, School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, People’s Republic of China
4
School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, People’s Republic of China
123
Journal of Combinatorial Optimization
Keywords Submodular maximization · Sequence · Streaming algorithm · Threshold
1 Introduction Maximization of submodular functions defined on a set of elements (Wu et al. 2019) has been well-studied in computer science, machine learning, economics, etc. In this model, given a submodular function defined on V and some specific-defined constraint I, the goal is to choose a subset S ∈ I from V, such that the value of the utility function is maximized. The following gives a brief summary for the maximization of submodular functions. For the submodular maximization with a cardinality constraint, Nemhauser et al. (Nemhauser et al. 1978) introduced a greedy procedure, which greedily selects the element with the maximum marginal gain in each iteration and obtains a (1 − e−1 )-approximation in O(nk) time, where n is the input size and k, an given integer, is the cardinality constraint. On the other hand, the work of Feige (1998) showed that, for any > 0, there does not exist any (1−e−
Data Loading...
