> Detailanzeige

Borassi, Michele [Verfasser:in] ; Epasto, Alessandro [Sonstige Person, Familie und Körperschaft]; Lattanzi, Silvio [Sonstige Person, Familie und Körperschaft]; Vassilvitskii, Sergei [Sonstige Person, Familie und Körperschaft]; Zadimoghaddam, Morteza [Sonstige Person, Familie und Körperschaft]

Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Book; Video
  • Titel: Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives
  • Beteiligte: Borassi, Michele [Verfasser:in]; Epasto, Alessandro [Sonstige Person, Familie und Körperschaft]; Lattanzi, Silvio [Sonstige Person, Familie und Körperschaft]; Vassilvitskii, Sergei [Sonstige Person, Familie und Körperschaft]; Zadimoghaddam, Morteza [Sonstige Person, Familie und Körperschaft]
  • Erschienen: [Erscheinungsort nicht ermittelbar]: ACM SIGMOD, 2019
  • Erschienen in: SIGMOD 2019 ; (Jan. 2019)
  • Umfang: 1 Online-Ressource (417 MB, 00:13:28:02)
  • Sprache: Englisch
  • DOI: 10.5446/42835
  • Identifikator:
  • Entstehung:
  • Anmerkungen: Audiovisuelles Material
  • Beschreibung: 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
  • Zugangsstatus: Freier Zugang
  • Rechte-/Nutzungshinweise: Namensnennung - Nicht kommerziell (CC BY-NC)