Ranking with submodular functions on a budget

DOI10.1007/S10618-022-00833-4zbMATH Open1497.68444arXiv2204.04168OpenAlexW4224692229MaRDI QIDQ2147409FDOQ2147409

Authors: Guangyi Zhang, Nikolaj Tatti, Aristides Gionis 

Publication date: 20 June 2022

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular functions has mainly been restricted in the context of selecting a set of items. On the other hand, many real-world applications require a solution that is a ranking over a set of items. The problem of ranking in the context of submodular function maximization has been considered before, but to a much lesser extent than item-selection formulations. In this paper, we explore a novel formulation for ranking items with submodular valuations and budget constraints. We refer to this problem as max-submodular ranking (MSR). In more detail, given a set of items and a set of non-decreasing submodular functions, where each function is associated with a budget, we aim to find a ranking of the set of items that maximizes the sum of values achieved by all functions under the budget constraints. For the MSR problem with cardinality- and knapsack-type budget constraints we propose practical algorithms with approximation guarantees. In addition, we perform an empirical evaluation, which demonstrates the superior performance of the proposed algorithms against strong baselines.

Full work available at URL: https://arxiv.org/abs/2204.04168

Recommendations

• scientific article; zbMATH DE number 6783452
• Adaptive submodular ranking
• Adaptive submodular ranking and routing
• Generalized budgeted submodular set function maximization
• Fast algorithms for maximizing submodular functions

zbMATH Keywords

dynamic programmingrankingapproximation algorithmssubmodular maximization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• 10.1162/jmlr.2003.3.4-5.993
• Title not available (Why is that?)
• An analysis of approximations for maximizing submodular set functions—I
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Approximating min sum set cover
• Multiple intents re-ranking
• Approximation algorithms for diversified search ranking
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• A unifying look at sequence submodularity
• Per-round knapsack-constrained linear submodular bandits
• Ranking with diverse intents and correlated contents
• Sequential Submodular Maximization and Applications to Ranking an Assortment of Products
• Adaptive submodular ranking
• Budget-constrained profit maximization without non-negative objective assumption in social networks

Uses Software

• UCI-ml
• MovieLens

This page was built for publication: Ranking with submodular functions on a budget

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2147409)