abstract

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint

Authors:

He HuangAuthors Info & Claims

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Pages 65 - 66

https://doi.org/10.1145/3410220.3453922

Published: 06 June 2021 Publication History

Abstract

Data summarization, a fundamental methodology aimed at selecting a representative subset of data elements from a large pool of ground data, has found numerous applications in big data processing, such as social network analysis [5, 7], crowdsourcing [6], clustering [4], network design [13], and document/corpus summarization [14]. Moreover, it is well acknowledged that the "representativeness" of a dataset in data summarization applications can often be modeled by submodularity - a mathematical concept abstracting the "diminishing returns" property in the real world. Therefore, a lot of studies have cast data summarization as a submodular function maximization problem (e.g., [2]).

Supplementary Material

MP4 File (SIGMETRICS21-fp141.mp4)

This talk is about the paper of ?Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint? accepted by ACM SIGMETRICS 2021. In this paper, we consider the fundamental problem of (non-monotone) submodular function maximization with a knapsack constraint, and propose simple yet effective and efficient algorithms for it. Specifically, we propose a deterministic algorithm with approximation ratio 6 and a randomized algorithm with approximation ratio 4, and show that both of them can be accelerated to achieve nearly linear running time. We also propose streaming algorithms with approximation ratios of 8+\epsilon and 6+\epsilon that make one pass and two passes over the data stream, respectively. As a by-product, we propose a two-pass streaming algorithm with an approximation ratio of 2+\epsilon when the considered submodular function is monotone. The extensive experimental results have demonstrated the superiorities of our algorithms.

Download
29.57 MB

References

[1]

Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenh"auser. 2020. Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. In Neural Information Processing Systems (NeurIPS), arXiv: 2007.05014.

[2]

Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2014. Streaming submodular maximization: Massive data summarization on the fly. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 671--680.

Digital Library

[3]

Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. 2010. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In International Workshop on Internet and Network Economics (WINE). 246--257.

[4]

Kai Han, Fei Gui, Xiaokui Xiao, Jing Tang, Yuntian He, Zongmai Cao, and He Huang. 2019. Efficient and Effective Algorithms for Clustering Uncertain Graphs. Proceedings of the VLDB Endowment, Vol. 12, 6 (2019), 667--680.

Digital Library

[5]

Kai Han, Yuntian He, Keke Huang, Xiaokui Xiao, Shaojie Tang, Jingxin Xu, and Liusheng Huang. 2020. Best Bang for the Buck: Cost-Effective Seed Selection for Online Social Networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 32, 12 (2020), 2297--2309.

[6]

Kai Han, He Huang, and Jun Luo. 2018a. Quality-Aware Pricing for Mobile Crowdsensing. IEEE/ACM Transactions on Networking, Vol. 26, 4 (2018), 1728--1741.

Digital Library

[7]

Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. 2018b. Efficient Algorithms for Adaptive Influence Maximization. Proceedings of the VLDB Endowment, Vol. 11, 9 (2018), 1029--1040.

Digital Library

[8]

Chien-Chung Huang and Naonori Kakimura. 2018. Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization. preprint, arXiv:1802.06212 (2018).

[9]

Chien-Chung Huang and Naonori Kakimura. 2019. Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. In Workshop on Algorithms and Data Structures (WADS). 438--451.

[10]

Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. 2020. Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, Vol. 82, 4 (2020), 1006--1032.

Digital Library

[11]

Andreas Krause and Daniel Golovin. 2014. Tractability: Practical Approaches to Hard Problems .Cambridge University Press. 71--104 pages.

[12]

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast Constrained Submodular Maximization: Personalized Data Summarization. In International Conference on Machine Learning (ICML). 1358--1367.

[13]

Gamal Sallam and Bo Ji. 2019. Joint placement and allocation of virtual network functions with budget and capacity constraints. In IEEE Conference on Computer Communications (INFOCOM). 523--531.

Digital Library

[14]

Adish Singla, Sebastian Tschiatschek, and Andreas Krause. 2016. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In AAAI Conference on Artificial Intelligence (AAAI). 2037--2043.

[15]

Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims. 2012. Temporal corpus summarization using submodular word coverage. In International Conference on Information and Knowledge Management (CIKM). 754--763.

Digital Library

[16]

Laurence A Wolsey. 1982. Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Mathematics of Operations Research, Vol. 7, 3 (1982), 410--425.

Digital Library

[17]

Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. 2020. "Bring your own greedy" + max: Near-optimal 1/2-approximations for submodular knapsack. In International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274.

Cited By

Tran TPham CHa DPham PLarson K(2024)Improved parallel algorithm for non-monotone submodular maximization under knapsack constraintProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/217(1961-1969)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/217
Cui SHan KTang SLi FLuo JBaeza-Yates RBonchi F(2024)Fairness in Streaming Submodular Maximization Subject to a Knapsack ConstraintProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671778(514-525)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671778

Index Terms

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint
1. Computing methodologies
  1. Machine learning
    1. Machine learning algorithms

Recommendations

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint
POMACS

Data summarization, i.e., selecting representative subsets of manageable size out of massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for submodular optimization, many of them incur large ...
Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint
SIGMETRICS '21

Data summarization, a fundamental methodology aimed at selecting a representative subset of data elements from a large pool of ground data, has found numerous applications in big data processing, such as social network analysis [5, 7], crowdsourcing [6], ...
Opinion Summarization via Submodular Information Measures
This paper focuses on opinion summarization for constructing subjective and concise summaries representing essential opinions of online text reviews. As previous works rarely focus on the relationship between opinions, topics, and sentences, we propose a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

May 2021

97 pages

ISBN:9781450380720

DOI:10.1145/3410220

General Chair:
Longbo Huang
Tsinghua University, China
,
Program Chairs:
Anshul Gandhi
Stony Brook University, USA
,
Negar Kiyavash
EPFL, Switzerland
,
Jia Wang
AT&T Labs Research, USA

ACM SIGMETRICS Performance Evaluation Review Volume 49, Issue 1
SIGMETRICS '21
June 2021
80 pages
ISSN:0163-5999
DOI:10.1145/3543516
Editor:
Nidhi Hegde
Borealis AI
Issue’s Table of Contents

Copyright © 2021 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2021

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

National Natural Science Foundation of China (NSFC)
National Key R&D Program of China

Conference

SIGMETRICS '21

Sponsor:

SIGMETRICS

SIGMETRICS '21: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 14 - 18, 2021

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tran TPham CHa DPham PLarson K(2024)Improved parallel algorithm for non-monotone submodular maximization under knapsack constraintProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/217(1961-1969)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/217
Cui SHan KTang SLi FLuo JBaeza-Yates RBonchi F(2024)Fairness in Streaming Submodular Maximization Subject to a Knapsack ConstraintProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671778(514-525)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671778

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten