Matroid secretary problem solved with improved algorithm for submodular goals
A Refined Analysis for Matroid Secretary with Submodular Objectives
Data Structures and Algorithms
Summary
The paper addresses a puzzle where you need to pick the best items one by one when they arrive in random order, but you can’t go back to change your choices. The goal is to maximize a complex kind of value that grows but with diminishing returns, called submodular. The authors propose a new approach that first learns from some early items, then picks others smartly based on how much value they add. Their method performs within about 8.7 times the optimal value and works for all sets obeying matroid rules.
What this means in practice
- •For online auction designers: Improve selection strategies that accept bids sequentially to maximize utility with interdependent values.
- •For wireless network planners: Optimize dynamic allocation of limited frequencies or channels with submodular benefits under uncertain arrivals.
A theory result. No direct application yet.
Authors
Dennis Joyce
Abstract
We study the matroid secretary problem with a nonnegative monotone submodular objective. Elements arrive in uniformly random order, and every acceptance decision is immediate and irrevocable. We give an $8.699$-competitive algorithm for arbitrary matroids. The algorithm first rejects a randomly sized initial segment of the arrival sequence as a learning set and runs submodular greedy on all elements in this set. Each later element receives a fixed weight equal to the marginal value it would have when inserted into the stored greedy sequence. On these fixed weights, the algorithm runs a linear-objective matroid secretary subroutine. The algorithm uses $O(nr)$ value queries and $O(n^2)$ independence queries, where $r$ is the matroid rank.