Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Ranking with submodular functions on the fly
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.ORCID-id: 0000-0002-1252-7489
HIIT, University of Helsinki.ORCID-id: 0000-0002-2087-5360
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.ORCID-id: 0000-0002-5211-112X
2023 (engelsk)Inngår i: 2023 SIAM International Conference on Data Mining, SDM 2023, SIAM , 2023, s. 604-612Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Maximizing submodular functions have been studied extensively for a wide range of subset-selection problems. However, much less attention has been given to the role of submodularity in sequence-selection and ranking problems. A recently-introduced framework, named maximum submodular ranking (MSR), tackles a family of ranking problems that arise naturally when resources are shared among multiple demands with different budgets. For example, the MSR framework can be used to rank web pages for multiple user intents. In this paper, we extend the MSR framework in the streaming setting. In particular, we consider two different streaming models and we propose practical approximation algorithms. In the first streaming model, called function arriving, we assume that submodular functions (demands) arrive continuously in a stream, while in the second model, called item arriving, we assume that items (resources) arrive continuously. Furthermore, we study the MSR problem with additional constraints on the output sequence, such as a matroid constraint that can ensure fair exposure among items from different groups. These extensions significantly broaden the range of problems that can be captured by the MSR framework. On the practical side, we develop several novel applications based on the MSR formulation, and empirically evaluate the performance of the proposed methods.

sted, utgiver, år, opplag, sider
SIAM , 2023. s. 604-612
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-350166ISI: 001284687600077Scopus ID: 2-s2.0-85180632410OAI: oai:DiVA.org:kth-350166DiVA, id: diva2:1883391
Konferanse
2023 SIAM International Conference on Data Mining, SDM 2023, Minneapolis, United States of America, Apr 27 2023 - Apr 29 2023
Merknad

Part of ISBN 9781611977653

QC 20240710

Tilgjengelig fra: 2024-07-10 Laget: 2024-07-10 Sist oppdatert: 2025-01-27bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Scopus

Person

Zhang, GuangyiGionis, Aristides

Søk i DiVA

Av forfatter/redaktør
Zhang, GuangyiTatti, NikolajGionis, Aristides
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 30 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf