Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives
| Autor: | Sergei Vassilvitskii, Silvio Lattanzi, Alessandro Epasto, Michele Borassi, Morteza Zadimoghaddam |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computer science
0102 computer and information sciences 02 engineering and technology Maximization 01 natural sciences Submodular set function Range (mathematics) Cardinality 010201 computation theory & mathematics Sliding window protocol Subadditivity 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Streaming algorithm Algorithm Standard model (cryptography) |
| Zdroj: | PODS |
| DOI: | 10.1145/3294052.3319701 |
| Popis: | The streaming computation model is a standard model for large-scale data analysis: the input arrives one element at a time, and the goal is to maintain an approximately optimal solution using only a constant, or, at worst, polylogarithmic space.In practice, however, recency plays a large role, and one often wishes to consider only the last w elements that have arrived, the so-called sliding window problem. A trivial approach is to simply store the last w elements in a buffer; our goal is to develop algorithms with space and update time sublinear in w. In this regime, there are two frameworks: exponential histograms and smooth histograms, which can be used to obtain sliding window algorithms for families of functions satisfying certain properties.Unfortunately, these frameworks have limitations and cannot always be applied directly. A prominent example is the problem of maximizing submodular function with cardinality constraints. While some of these difficulties can be rectified on a case-by-case basis, here, we describe an alternative approach to designing efficient sliding window algorithms for maximization problems. Then we instantiate this approach on a wide range of problems, yielding better algorithms for submodular function optimization, diversity optimization and general subadditive optimization. In doing so, we improve state-of-the art results obtained using problem-specific algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|