The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and Strictly Between 1/e and 1/2 in General
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Submodular Secretary Problem".
Jane: Here's the gist of the paper. The paper addresses the submodular secretary problem with a cardinality constraint, where n elements arrive in a uniformly random order, and an algorithm must irrevocably accept or reject each element to maximize a non-negative submodular function over sets of at most k elements.
Tom: For monotone objectives, the optimal competitive ratio converges exactly to 1 - 1/e as k to infinity, and the worst-case ratio over all budgets is exactly 1/e.
Jane: This bound is achievable by a single algorithm using at most 4n + 1 value queries.
Tom: For general objectives, where previous best results were around 0.107, the optimal limiting ratio lies strictly between 1/e and 1/2.
Title and authors: Tom: So we're looking at this paper today called "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/e and one/two in General <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>." It tackles this problem where you get n elements one by one, and you have to pick the best ones up to a budget of k. The title is pretty precise about what it does with monotone functions versus general ones.
Jane: That's right, Tom. And what's interesting is that for monotone objectives, they settle the problem completely: the best possible competitive ratio goes exactly to one minus one over e as the budget k gets bigger than infinity. But for general objectives, things are a bit more nuanced because the ratio stays strictly between one over e and zero point five as k grows.
Lu: The paper sets up a lot of hard limits here. For monotone functions, they find that even with unlimited computation, you can't do better than one minus one over e in the long run, and this worst case is reached when you only have a budget of k equals one. But for general functions, they show that the optimal limit isn't zero point five; it's somewhere right above one over e.
Meng: From my side, I’m curious about how much computation we need to actually achieve those bounds. The paper mentions that for monotone objectives, you can get that one minus one over e ratio with at most four n plus one value queries, which sounds pretty efficient for a complex problem like this. But what about when the functions are general?
Lalam: For the general case, they show an algorithm exists that only needs to know n and k and makes polynomially many value queries, and this gives a ratio of at least one over e plus three point five times ten to the negative six for any non-negative function when k is large enough. This is a big improvement over previous results which were way worse.
Tom: That's a tiny constant improvement, but it's still a concrete number that gives us something to work with for general cases. Jane, how does that compare to what we used to think was possible before this paper?
Jane: Before this paper, the best known ratios for general objectives were hovering around zero point one zero seven for the limit when k was large. This new result shows that the optimal limit is strictly between one over e and zero point five, which is a significant gap in our understanding of what's achievable.
Lu: The authors also found a specific ratio they can guarantee at every budget level k, which is zero point two six seven seven when k equals twenty-six or so. That shows that even for small budgets, there's a solid floor we can expect, rather than just relying on asymptotic limits.
Title and authors: Meng: That floor sounds more practical for deployment because it gives you a guarantee across all scales of your budget constraint. But what about the practical cost of getting that zero point two six seven seven ratio in real-world scenarios? Is it feasible to run that kind of algorithm when the input size n is really massive?
Lalam: The paper mentions a specific algorithm called eligibility attenuation, which is a key part of their method, and they show it can get close to one over e for large budgets k. This mechanism involves accepting an element based on whether it passed a price test at an earlier time and how long ago that was.
Tom: Eligibility attenuation sounds like a sophisticated way to handle the online decision-making process under these constraints. So, if you're driving and you see something interesting, this algorithm tries to figure out if it's better than what you already saw without having to look at everything again.
Jane: Exactly. And when we look at the specific mechanism they describe in eligibility attenuation, it ensures that the probability of an element already being selected is exactly one minus e minus tau, where tau is the total time during which it would have passed before. That sounds like a very tight probabilistic control over acceptance decisions.
Lu: What I find compelling about their approach for general objectives is how they distinguish between monotone and general functions, showing that attenuation isn't even necessary for monotone objectives because the ratio there is determined exactly by that offline benchmark of one minus e plus or minus a small term.
Meng: That makes sense. If the structure of the function doesn't change, you don't need this complex probabilistic mechanism to get near optimal performance; it’s more deterministic. But when things get general, the non-monotonic parts are what force us into that gap between one over e and zero point five.
Lalam: And they found that for general objectives, no algorithm can actually achieve a ratio better than approximately zero point four nine seven zero five three when k is large. This sets a hard ceiling on what's possible with current methods, which is important for setting realistic expectations in the field.
Tom: That ceiling number is pretty sobering when you think about how much work it takes to push past it. But then they showed that their specific randomized algorithm for general objectives achieves one over e plus three point five times ten to the negative six for every non-negative function, no matter what.
Jane: So the improvement they show isn't just in the asymptotic limit, but a concrete guarantee of being slightly better than one over e plus that small constant for large budgets k. That gives us a much more reliable expectation when we are dealing with larger budget constraints.
Title and authors: Lu: And they also provided some hardness results, which is always useful. They showed that for every budget k greater than or equal to two and any small positive number epsilon, there's an instance of a monotone coverage problem where the ratio is at most one minus one over k times k plus epsilon.
Meng: Hardness results are important because they tell us exactly how hard the problem is to solve, which helps us know where our efforts should be focused. The bound they showed for large k, that one minus one over e plus O log log k over log k, suggests that as the budget grows very big, getting closer to the ideal limit becomes progressively harder.
Lalam: It seems like this paper really solidifies the understanding of where the theoretical limits lie for both monotone and general submodular secretary problems with a cardinality constraint. The main contribution is providing explicit guarantees across different budgets, moving beyond just asymptotic results that only apply when k goes to infinity.
Tom: So, to wrap up on "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/e and one/two in General," we have established tight bounds for both function types and shown that eligibility attenuation is a strong tool for general objectives <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>. It gives us concrete ratios like zero point two six seven seven at every budget level k.
Jane: Exactly. For the listener, it means if you're designing a system that needs to select a small set of items from an incoming stream, you can now have a much clearer idea of what performance you can actually expect based on the function type and how large your selection budget is.
Lu: It’s about understanding that there are fundamental structural differences between monotone and general problems that dictate the achievable competitive ratios. The work highlights that for general problems, the non-monotonicity is a real barrier we have to contend with.
Meng: For me, it’s about knowing what to expect when I’m building something at scale. Knowing that there’s a ceiling of zero point four nine seven zero five three for the best known algorithms gives me a realistic target when trying to deploy a solution.
Lalam: And the algorithm itself, eligibility attenuation, is a mechanism we can actually use in practice to get close to the theoretical limits, especially when k is large. It’s not just abstract math; it’s a tool.
Tom: So that's where we are with this paper. We have bounds for monotone problems settled exactly at one minus one over e and a better lower bound for general problems, and we have an algorithm that gets us close to those limits with concrete performance guarantees across various budgets k. That's the gist of "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/two in General <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>."
The paper's summary: Tom: So, we just talked about how this paper settles the theoretical limits for picking items when you have to pick up to a certain number of them from an incoming stream.
Jane: Yeah, so basically, they’re saying that for problems where the value function is monotone—meaning adding more items never hurts—they found the absolute best possible ratio is exactly one minus one over e. That's a very tight bound.
Lu: And for those monotone problems, they show you can actually hit that one minus one over e limit using just about four times the number of items in your stream, which is quite efficient computationally.
Meng: That sounds great theoretically, but what does that mean for me when I'm actually running this on a live system? Does "four times the number of items" mean anything practical with millions of incoming data points?
Lalam: The paper suggests a specific strategy called eligibility attenuation. It’s a way to make the decision at each step based on how long ago an item was available, and it keeps that ratio locked onto one minus one over e for large budgets.
Tom: So, for monotone objectives, the method is pretty straightforward—use that attenuation rule and you get near-perfect performance asymptotically as the budget gets huge. But then they switch gears to general objectives—where the value function can go up and down.
Jane: That’s where things get interesting because for general functions, they say you can't hit that perfect one minus one over e limit in the same way; the best ratio stays strictly between one over e and zero point five as the budget size grows.
Meng: So even with a huge budget, you can't guarantee that perfect performance if your value function isn't monotone? That sounds like a big deal for deployment—it means we have to accept some gap.
Lu: Exactly. They show that their randomized algorithm for general objectives achieves one over e plus a very tiny constant, three point five times ten to the negative six, every time you test it on any non-negative function as long as your budget size is big enough.
Lalam: And they also gave us some hard limits on what’s possible with current techniques; no algorithm can ever beat a ratio of zero point four nine seven zero five three when the budget is large. That sets a very clear ceiling on performance for general problems right now.
Tom: It sounds like the paper gives us two different answers depending on the function type: perfect performance if it's monotone, and an improved but still bounded performance for everything else.
Jane: And they showed that there are specific rules, like the eligibility attenuation strategy, that work well for general problems, even if they can't hit the absolute best theoretical limit.
Lu: The main thing to watch is how those hard limits change as you look at different budget sizes; the performance gap between one over e and zero point five gets smaller as you increase the budget size significantly.
Meng: It’s helpful to know that there’s a solid floor, like zero point two six seven seven for small budgets, so we don't expect total failure when we start out with a small selection limit.
Lalam: So it turns out that even though general problems are harder, the structure of the problem still lets you get close to one over e if you use the right probabilistic mechanism.
Tom: This paper really clarifies that for any online selection problem with a budget constraint, you need to know if your objective is monotone or not because those two scenarios have fundamentally different theoretical answers.
Jane: And it points us toward using tools like eligibility attenuation as a robust way to handle the uncertainty in general objectives.
The paper's improvements: Tom: So we've talked about the paper’s main results—that monotone objectives hit that perfect one minus one over e limit, while general objectives get stuck somewhere between one over e and zero point five.
Jane: Yeah, so the paper points out a few ways they can push these results even further, especially for those general problems where things are messy.
Lu: They suggest using eligibility attenuation as a primary ingredient because it’s a very strong tool for controlling the acceptance probability in those complex settings.
Meng: Eligibility attenuation is that mechanism where you decide whether to take something based on how long ago it was available, and they show this helps you get closer to one over e for large budgets.
Tom: That sounds like a practical improvement because it gives us a concrete algorithm instead of just an asymptotic theoretical limit.
Jane: Exactly, and they also look at variants of that rule, like the uniform variant or the insured price policy, to see which ones work best for different kinds of general functions.
Lu: They even show that for monotone problems, you don't even need attenuation because the ratio is determined exactly by an offline benchmark of one minus e plus some small term.
Meng: That’s a nice simplification; if the function structure doesn't change, you can rely on a simpler approach instead of running a complex probabilistic test every time.
Tom: The paper also provides some new hardness results that show exactly how hard it is to solve these problems for certain budget sizes and function types.
Jane: These hardness results give us the numbers we need to understand the difficulty, showing how close you can get to one minus one over k times k for monotone problems when the budget size is small.
Lu: And they also showed that for larger budgets, like when the budget is bigger than sixty four, it gets progressively harder to get closer to that ideal limit of one minus e plus a little correction term.
Meng: So, if you're trying to build something for a real application, knowing these hardness results helps you understand the trade-off between how good your algorithm is and how much computing time or data you have.
Tom: The authors also show that their specific randomized algorithm for general objectives gets us one over e plus three point five times ten to the negative six for any non-negative function when the budget size is large enough.
Jane: That tiny constant improvement means that even with those messy general functions, you can be almost as good as the best possible monotone case once your budget is quite large.
Lu: It’s a lot of work to prove those explicit guarantees across all budgets, but they lay out a solid framework for how to approach these secretary problems systematically.
Meng: So what this means for us is that we have better tools now—a clearer understanding of the limits and an algorithm that actually performs well in the general case, even if it’s not perfect.
Conclusion: Tom: So we’re wrapping up on "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/two in General." Basically, this paper gives us the tightest bounds ever we've seen for selecting items when you have a budget constraint.
Jane: Right, so to recap it’s about showing that monotone problems are perfect at one minus one over e and general problems get stuck somewhere between one over e and zero point five.
Lu: The paper really highlights the structural difference between those two types of functions because that difference dictates everything about what competitive ratio is achievable.
Meng: It changes things for deployment because it tells us exactly how much performance gap we have to plan for depending on whether our data stream has a predictable structure or not.
Lalam: I’m pretty sure this result, especially the explicit guarantees across all budget sizes, means we can start designing systems with more confidence about their worst-case performance.
Tom: It does sound like it gives us a better roadmap for building those selection models that really balances theoretical perfection against practical performance on real traffic.
Jane: I think the biggest thing is how they connected the abstract math to things like eligibility attenuation, which is a mechanism we can actually use in practice to get near optimal results for general problems.
Lu: That's a key part of it; it’s not just finding a number, it’s giving you a concrete tool to use when you have those non-monotone functions.
Meng: I'm still worried about the computational cost of running that attenuation rule on massive streams, but knowing it pushes us closer to one over e is worth the effort.
Tom: It is; and it sets a new benchmark for what we consider achievable when dealing with online selection under constraints.
Jane: So this paper really solidifies where we stand on this problem, moving us past just vague guesses about performance limits.
Lu: It opens up a lot of avenues for future work, especially looking at how these results might apply to different types of data structures or maybe even more complex selection scenarios.
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
University of Maryland, College Park
cs.DS, cs.GT
Submitted: 2026-11-12
Updated: 2026-11-12
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 87/100
The gist: The paper addresses the submodular secretary problem with a cardinality constraint, where n elements arrive in a uniformly random order…
Key concepts
- Submodular Secretary Problem with Cardinality Constraint
- This problem involves a sequence of $n$ items arriving randomly. The goal is to select at most $k$ items from this sequence to maximize the total value derived from them, where the value function exhibits submodularity. Each item must be accepted or rejected irrevocably.
- Monotone Objectives
- In this context, a monotone objective means that adding more items to a chosen set never decreases the total value. This property simplifies analysis significantly, allowing for an exact competitive ratio of $1 - 1/e$ as $k$ grows.
- Eligibility Attenuation (AttenuatedPricing)
- This is a specific algorithmic technique where an element passing a price test at time $t$ is accepted with probability $e - au$. Here, $ au$ represents the total time during which that element could have passed. This mechanism precisely controls the probability of having already selected an item.
- Competitive Ratio ($ ho_k$)
- The competitive ratio measures how close an algorithm's performance is to the optimal solution. A ratio of $1/e$ means the algorithm achieves at least that fraction of the optimal value. The paper shows this ratio depends heavily on whether the objective is monotone or general.
Terminology
Summary
The paper addresses the submodular secretary problem with a cardinality constraint, where n elements arrive in a uniformly random order, and an algorithm must irrevocably accept or reject each element to maximize a non-negative submodular function over sets of at most k elements. p. 0 The Submodular Secretary Problem:
Tight 1 − 1/e for Monotone Objectives,
and Strictly Between 1/e and 1/2 in General
Hamed Abdi∗ Kiarash Banihashem† MohammadTaghi Hajiaghayi‡
Danny Mittal§
November 2026
Abstract
In the submodular secretary problem with a cardinality constraint, n elements arrive in
uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival
so as to maximize a nonnegative submodular function over sets of at most k elements. For
monotone objectives we settle the problem: the optimal competitive ratio tends to exactly
1 − 1/e as k → ∞, and its worst case over all budgets k is exactly 1/e.Where the paper says it
For monotone objectives, the optimal competitive ratio converges exactly to 1 - 1/e as k to infinity, and the worst-case ratio over all budgets is exactly 1/e. p. 0 The Submodular Secretary Problem:
Tight 1 − 1/e for Monotone Objectives,
and Strictly Between 1/e and 1/2 in General
Hamed Abdi∗ Kiarash Banihashem† MohammadTaghi Hajiaghayi‡
Danny Mittal§
November 2026
Abstract
In the submodular secretary problem with a cardinality constraint, n elements arrive in
uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival
so as to maximize a nonnegative submodular function over sets of at most k elements. For
monotone objectives we settle the problem: the optimal competitive ratio tends to exactly
1 − 1/e as k → ∞, and its worst case over all budgets k is exactly 1/e. For
monotone objectives we settle the problem: the optimal competitive ratio tends to exactly
1 − 1/e as k → ∞, and its worst case over all budgets k is exactly 1/e. The bound 1 − 1/e
cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm
with at most 4n + 1 value queries; previously the best ratio without a shortlist was 1/e − o(1),
with exponentially many queries.Where the paper says it
Where the paper says it
For general objectives, where previous best results were around 0. p. 3 Objective Previous best (no shortlist) This paper Upper bound
Monotone 1/e − o(1) [KT17] (exponential queries); 0. 275 − o(1)
[KT17] (polynomial queries)
1−1/e−o(1); 1/e
for every k
1 − 1/e + o(1) (Theorem 1. For general objectives, where the best known ratio was about
0. 107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve
1/e + 3. For general objectives, where the best known ratio was about
0. 107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve
1/e + 3. 107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve
1/e + 3. 5 · 10−6
for large k, and no algorithm achieves more than 0.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Hardness results indicate that for every k at least 2 and epsilon > 0, there exists a monotone coverage instance with budget k where the ratio is at most 1 - (1 - 1/k)k + epsilon. p. 1 Let A be any randomized online algorithm, with unlimited computation
and unlimited queries on subsets of arrived elements. (a) For every k ≥ 2 and ε > 0, there is a monotone coverage instance with budget k on which A
has ratio at most 1 − (1 − 1/k)
k + ε. Let A be any randomized online algorithm, with unlimited computation
and unlimited queries on subsets of arrived elements. (a) For every k ≥ 2 and ε > 0, there is a monotone coverage instance with budget k on which A
has ratio at most 1 − (1 − 1/k)
k + ε.Where the paper says it
Where the paper says it
Explicit guarantees are provided across various budgets:
-
Monotone Objectives: The ratio is guaranteed to be at least 1/e for every budget k.
-
General Objectives: Theorem A.1 provides explicit guarantees at every budget k, with ratios ranging from a minimum of 0. p. 3
2677 for small k up to approaching 1/e as k at least 1012. p. 3Where the paper says it
4 take effect only for large k. We also give explicit guarantees at every budget, with no error term, uniformly in n ≥ k.
Specific policies mentioned include the eligibility attenuation algorithm (AttenuatedPricing) which achieves ratios approaching 1/e for large k, and simpler rules like the singleton rule, two-pick rule, or multi-rank rules. p. 3Where the paper says it
For general objectives, some algorithm making at most 6n + 1 value queries has ratio at least 0. 2677 for every k; the ratio is at least 0.
Where the paper says it
3676 for k ≥ 106 (Theorem A. It uses two picks for k ≤ 3, for 4 ≤ k ≤ 29 a multi-rank secretary rule that is restarted after every stop on a geometric time grid, and Poisson-tail prices with eligibility attenuation for larger k.
The core algorithmic contribution is eligibility attenuation: an element passing a price test at time t is accepted with probability e - tau, where tau is the total earlier time during which it would have passed. p. 0 2677 at every budget. The main new ingredient of our algorithm is eligibility attenuation: an
element that passes the price test at time t is accepted with probability e
−τ
, where τ is the total
earlier time during which it would have passed, which makes the probability that it has already
been selected exactly 1 − e
−τ
. 2677 at every budget. The main new ingredient of our algorithm is eligibility attenuation: an
element that passes the price test at time t is accepted with probability e
−τ
, where τ is the total
earlier time during which it would have passed, which makes the probability that it has already
been selected exactly 1 − e
−τ
.Where the paper says it
Where the paper says it
Theorem 5.1 demonstrates a randomized algorithm for general objectives that makes polynomially many value queries and satisfies E[f(A)] at least 1/e + 3. p. 2 4 (Beyond 1/e). There is a randomized algorithm that knows only n and k, accepts at
most k elements, and makes polynomially many value queries on subsets of arrived elements, whose
ratio on nonnegative submodular objectives is at least 1/e + 3. There is a randomized algorithm for the submodular secretary problem
with a cardinality constraint that knows only n and k, accepts at most k elements on every execution,
makes at most 4n + 1 value queries, each on a subset of the elements that have arrived, and satisfies
the following, uniformly over n ≥ k and f. (a) If f is nonnegative and submodular, then E[f(A)] ≥
1/e − O(log2
(k + 1)/k)
OPT.Where the paper says it
Where the paper says it
The analysis distinguishes between monotone and general objectives: attenuation is unnecessary for monotone objectives, as the ratio is determined exactly by the offline benchmark of 1 - e - o(1) for large k. p. 2 So the limiting ratio for general objectives lies strictly between 1/e and 1/2, and in particular
strictly below the monotone limit 1 − 1/e; the lower bound is achieved with polynomially many
queries. Offline, unlimited queries solve the problem exactly, and so these barriers are purely a
consequence of online decisions. In the other direction, there is a barrier strictly below 1−1/e, which comes from nonmonotonicity. 5 (General objectives).Where the paper says it
Where the paper says it
Various variants of algorithms are analyzed, including the uniform variant, exempt variant, and insured price policy. p. 3 3696 for every k ≥ 2, and
more than 1
2
for every k ≥ 98 (Theorem B. It uses exact optimization over the observed prefix for
k ≤ 21, with O(n
21) queries, for 22 ≤ k < 106 a price policy mixed with the single-choice rule, with
at most n + 1 queries, and for larger k a variant of AttenuatedPricing. (b) For every k ≥ 64, there is a monotone coverage instance with budget k and at most k
2
elements
on which A has ratio at most 1 − 1/e + O(log log k/ log k). Unlike the offline barrier of [NW78], Theorem 1. Offline, Feige, Mirrokni,
and Vondrák [FMV11] prove a 1/2 barrier for unconstrained maximization with polynomially many
queries, a bound of the same value as our pairwise barrier but with a different source, namely query
complexity. 1 shows that the limiting ratio 1 − 1/e of the shortlist algorithm in [ASS19]
can be achieved with no shortlist, and Theorem 1. 107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve
1/e + 3. 5 · 10−6
for large k, and no algorithm achieves more than 0. 4 (Beyond 1/e). There is a randomized algorithm that knows only n and k, accepts at
most k elements, and makes polynomially many value queries on subsets of arrived elements, whose
ratio on nonnegative submodular objectives is at least 1/e + 3. We also give explicit guarantees
at every budget, with no error term, uniformly in n ≥ k. For general objectives, some algorithm
making at most 6n + 1 value queries has ratio at least 0. The bound 1 − 1/e
cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm
with at most 4n + 1 value queries; previously the best ratio without a shortlist was 1/e − o(1),
with exponentially many queries. For general objectives, where the best known ratio was about
0.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve online selection for monotone objectives by using AttenuatedPricing to achieve an asymptotic competitive ratio of exactly 1 minus 1/e, even with unlimited computation and a polynomial number of queries (at most 4n + 1).
-
Enhance general-purpose submodular maximization algorithms to achieve a competitive ratio strictly between 1/e and the upper bound of approximately 0.497053 for large budgets k, using eligibility attenuation as the main new ingredient.
-
Develop a robust system for general objectives that guarantees an expected competitive ratio of at least 1/e plus a tiny constant (3.5 x 10-6) for all sufficiently large k, using a mixture of Greedy restricted to promising elements and AttenuatedPricing.
-
Implement budget-aware policies that provide certified competitive ratios for general objectives at every budget level k, such as achieving ratios of at least 0.2677 for small budgets and exceeding 1/e for sufficiently large k.
-
Create a system that can solve the submodular secretary problem with cardinality constraints by leveraging the structural results from matroid theory, allowing it to achieve constant competitive ratios for every matroid constraint instance.
Abstract
In the submodular secretary problem with a cardinality constraint, n elements arrive in uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival so as to maximize a nonnegative submodular function over sets of at most k elements. For monotone objectives we settle the problem: the optimal competitive ratio tends to exactly 1-1/e as k to infinity, and its worst case over all budgets k is exactly 1/e. The bound 1-1/e cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm with at most 4n+1 value queries; previously the best ratio without a shortlist was 1/e-o(1), with exponentially many queries. For general objectives, where the best known ratio was about 0.107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve 1/e+3.5 times10-6 for large k, and no algorithm achieves more than 0.497053. We also achieve 0.2677 at every budget. The main new ingredient of our algorithm is eligibility attenuation: an element that passes the price test at time t is accepted with probability e-τ, where τ is the total earlier time during which it would have passed, which makes the probability that it has already been selected exactly 1-e-τ.
Sources
- As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet
- An improved algorithm for the submodular secretary problem with a cardinality constraint
- Cardinality constrained submodular maximization for random streams
- Improved Submodular Secretary Problem with Shortlists
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time