kth.sePublikationer KTH
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Ingår i: 2023 SIAM International Conference on Data Mining, SDM 2023, SIAM , 2023, s. 604-612Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
SIAM , 2023. s. 604-612
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-350166ISI: 001284687600077Scopus ID: 2-s2.0-85180632410OAI: oai:DiVA.org:kth-350166DiVA, id: diva2:1883391
Konferens
2023 SIAM International Conference on Data Mining, SDM 2023, Minneapolis, United States of America, Apr 27 2023 - Apr 29 2023
Anmärkning

Part of ISBN 9781611977653

QC 20240710

Tillgänglig från: 2024-07-10 Skapad: 2024-07-10 Senast uppdaterad: 2025-01-27Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Scopus

Person

Zhang, GuangyiGionis, Aristides

Sök vidare i DiVA

Av författaren/redaktören
Zhang, GuangyiTatti, NikolajGionis, Aristides
Av organisationen
Teoretisk datalogi, TCS
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 30 träffar
RefereraExporteraLänk till posten
Permanent länk

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