Skip to main navigation Skip to search Skip to main content

Streaming Algorithms for Maximizing DR-Submodular Functions with d-Knapsack Constraints

  • Ocean University of China
  • Rutgers - The State University of New Jersey, Newark

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The problem of maximizing submodular functions has received considerable attention in the last few years. However, most of the submodular functions are defined on set. But recently some progress has been made on the integer lattice. In this paper, we study streaming algorithms for the problem of maximizing DR-submodular functions with d-knapsack constraints on the integer lattice. We first propose a one pass streaming algorithm that achieves a 1-θ1+d -approximation with O(log(dβ-1)βϵ) memory complexity and O(log(dβ-1)ϵlog‖b‖∞) update time per element, where θ= min (α+ ϵ, 0.5 + ϵ) and α, β are the upper and lower bounds for the cost of each item in the stream. Then we devise an improved streaming algorithm to reduce the memory complexity to O(dβϵ) with unchanged approximation ratio and query complexity. As far as we know, this is the first streaming algorithm on the integer lattice under this constraint.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
EditorsWeili Wu, Hongwei Du
PublisherSpringer Science and Business Media Deutschland GmbH
Pages159-169
Number of pages11
ISBN (Print)9783030931759
DOIs
StatePublished - 2021
Externally publishedYes
Event15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021 - Virtual, Online
Duration: Dec 20 2021 → Dec 22 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13153 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
CityVirtual, Online
Period12/20/21 → 12/22/21

ASJC Scopus Subject Areas

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • d-Knapsack constraints
  • DR-submodular maximization
  • Integer lattice
  • Streaming algorithm

Fingerprint

Dive into the research topics of 'Streaming Algorithms for Maximizing DR-Submodular Functions with d-Knapsack Constraints'. Together they form a unique fingerprint.

Cite this