Interactive optimization of submodular functions under matroid constraints

DOI10.1007/978-3-030-87756-9_20MaRDI QIDQ2695451zbMATH OpenOpenAlexFDO

Authors Nawal Benabbou, Cassandre Leroy, Thibaut Lust, Patrice Perny

Publication date 31 March 2023

Full work available at URL https://doi.org/10.1007/978-3-030-87756-9_20

zbMATH Keywords

local searchmatroidsubmodular functionpreference elicitationgreedy search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Decision theory (91B06) Social choice (91B14) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matching models (91B68)

Recommendations

• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Approximation algorithm and its performance for maximizing submodular function subject to matroid intersection
• Non-monotone submodular maximization under matroid and knapsack constraints

Cites work

• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• An analysis of approximations for maximizing submodular set functions—I
• Combinatorial auctions with decreasing marginal utilities
• Computing approximate solutions of the maximum covering problem with GRASP
• Constraint-based optimization and utility elicitation using the minimax decision criterion
• Finding a collective set of items: from proportional multirepresentation to group recommendation
• Matroids and the greedy algorithm
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Maximizing a class of submodular utility functions
• Maximizing a monotone submodular function subject to a matroid constraint
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• Optimal approximation for the submodular welfare problem in the value oracle model
• Some Abstract Pivot Algorithms

Cited in

(2)

• Using atomic bounds to get sub-modular approximations
• On the enumeration of non-dominated matroids with imprecise weights

This page was built for publication: Interactive optimization of submodular functions under matroid constraints

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