TY - GEN
T1 - Data Summarization Beyond Monotonicity
T2 - 16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023
AU - Tang, Shaojie
N1 - Publisher Copyright:
© 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2024
Y1 - 2024
N2 - The objective of a two-stage submodular maximization problem is to reduce the ground set using provided training functions that are submodular, with the aim of ensuring that optimizing new objective functions over the reduced ground set yields results comparable to those obtained over the original ground set. This problem has applications in various domains including data summarization. Existing studies often assume the monotonicity of the objective function, whereas our work pioneers the extension of this research to accommodate non-monotone submodular functions. We have introduced the first constant-factor approximation algorithms for this more general case.
AB - The objective of a two-stage submodular maximization problem is to reduce the ground set using provided training functions that are submodular, with the aim of ensuring that optimizing new objective functions over the reduced ground set yields results comparable to those obtained over the original ground set. This problem has applications in various domains including data summarization. Existing studies often assume the monotonicity of the objective function, whereas our work pioneers the extension of this research to accommodate non-monotone submodular functions. We have introduced the first constant-factor approximation algorithms for this more general case.
UR - https://www.scopus.com/pages/publications/85180528829
U2 - 10.1007/978-3-031-49611-0_20
DO - 10.1007/978-3-031-49611-0_20
M3 - Conference contribution
AN - SCOPUS:85180528829
SN - 9783031496103
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 277
EP - 286
BT - Combinatorial Optimization and Applications - 16th International Conference, COCOA 2023, Proceedings
A2 - Wu, Weili
A2 - Guo, Jianxiong
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 15 December 2023 through 17 December 2023
ER -