kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Ranking with submodular functions on the fly
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1252-7489
HIIT, University of Helsinki.ORCID iD: 0000-0002-2087-5360
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5211-112X
2023 (English)In: 2023 SIAM International Conference on Data Mining, SDM 2023, SIAM , 2023, p. 604-612Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
SIAM , 2023. p. 604-612
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-350166ISI: 001284687600077Scopus ID: 2-s2.0-85180632410OAI: oai:DiVA.org:kth-350166DiVA, id: diva2:1883391
Conference
2023 SIAM International Conference on Data Mining, SDM 2023, Minneapolis, United States of America, Apr 27 2023 - Apr 29 2023
Note

Part of ISBN 9781611977653

QC 20240710

Available from: 2024-07-10 Created: 2024-07-10 Last updated: 2025-01-27Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records

Zhang, GuangyiGionis, Aristides

Search in DiVA

By author/editor
Zhang, GuangyiTatti, NikolajGionis, Aristides
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf