Interactive optimization of submodular functions under matroid constraints

DOI10.1007/978-3-030-87756-9_20OpenAlexW3208987086MaRDI QIDQ2695451FDOQ2695451

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

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

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)

Cites Work

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

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)