Strong Algorithms for the Ordinal Matroid Secretary Problem∗
José A. Soto†

Abner Turkieltaub‡

Victor Verdugo§

arXiv:1802.01997v1 [] 6 Feb 2018

Abstract
In contrast with the standard and widely studied utility variant, in the ordinal Matroid Secretary
Problem (MSP) candidates do not reveal numerical weights but the decision maker can still
discern if a candidate is better than another. We consider three competitiveness measures for the
ordinal MSP. An algorithm is α ordinal-competitive if for every weight function compatible with
the ordinal information, the expected output weight is at least 1/α times that of the optimum; it
is α intersection-competitive if its expected output includes at least 1/α fraction of the elements
of the optimum, and it is α probability-competitive if every element from the optimum appears
with probability 1/α in the output. This is the strongest notion as any α probability-competitive
algorithm is also α intersection, ordinal and utility (standard) competitive.
Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitive ratios on many matroid classes. In fact, we improve upon the guarantees for almost every matroid class considered in the MSP literature:
we achieve probability-competitive ratios of e for transversal matroids (matching Kesselheim et
a stronger notion); of 4 for graphic matroids (improving on 2e by Korula
al. [29], but under √
and Pál [33]); of 3 3 ≈ 5.19 for laminar matroids (improving on 9.6 by Ma et al. [39]); and
of k k/(k−1) for a superclass of k column sparse matroids, improving on the ke result by Soto
[44]. We also get constant ratios for hypergraphic matroids, for certain gammoids and for graph
packing matroids that generalize matching matroids. The forbidden sets technique is inspired
by the backward analysis of the classical secretary problem algorithm and by the analysis of
the e-competitive algorithm for online weighted
bipartite matching by Kesselheim et al. [29].
p
1/ρ) utility-competitive algorithm for uniform maAdditionally, we modify Kleinberg’s 1 + O( p
troids of rank ρ in order to obtain a 1 + O( log ρ/ρ) probability-competitive algorithm. Our
second contribution are algorithms for the ordinal MSP on arbitrary matroids. We devise an
O(1) intersection-competitive algorithm, an O(log ρ) probability-competitive algorithm and an
O(log log ρ) ordinal-competitive algorithm for matroids of rank ρ. The last two results are based
on the O(log log ρ) utility-competitive algorithm by Feldman et al. [19].

1

Introduction

In the classical secretary problem (see, e.g., [21] for a survey) an employer wants to select exactly
one out of n secretaries arriving in random order. After each arrival, the employer learns the
relative merits of the new candidate (i.e., he can compare the candidate with previous ones but no
numerical quantity is revealed), and must reject or accept immediately. Lindley [36] and Dynkin
[16] show that the strategy of sampling 1/e fraction of the candidates and then selecting the first
record has a probability of at least 1/e of selecting the best secretary and that no algorithm can beat
this constant. During the last decade, generalizations of this problem have attracted the attention
of researchers, specially due to applications in online auctions and online mechanism design.
∗

This work was partially supported by FONDECYT project 11130266, Conicyt PCI PII 20150140 and Núcleo
Milenio Información y Coordinación en Redes ICM/FIC RC130003
†
Departamento de Ingenierı́a Matemática & CMM, Universidad de Chile. Email: jsoto@dim.uchile.cl
‡
Departamento de Ingenierı́a Matemática, Universidad de Chile. Email: abnerturkieltaub@gmail.com
§
Departamento de Ingenierı́a Industrial, Universidad de Chile & Départment d’Informatique CNRS UMR 8548,
École normale supérieure, PSL Research University. Email: vverdugo@dii.uchile.cl

1

Arguably the most natural extension is the generalized secretary problem by Babaioff et al. [5].
In their setting, a set R of candidates of known size is presented to an algorithm on uniform random
order. On arrival, each element r reveals its hidden weight w(r) and the algorithm must irrevocably
decide whether to select it or not while preserving the independence of the set of selected elements
on a given independence system1 (R, I). The objective is to maximize the total weight of the
selected independent set. Mainly motivated by applications and by the richness of their structural
properties, Babaioff et al. focuses on the case in which (R, I) is a matroid 2 , where this problem
takes the name of Matroid Secretary Problem (MSP). An α competitive algorithm (which we call
α utility-competitive algorithm to differentiate it from other measures) is one that returns an
independent set whose expected weight is at least 1/α times the weight of an optimum independent
set. Babaioff et al. posts the well-known, and still open, Matroid Secretary Conjecture which in
its weak form states that there must be a constant competitive algorithm for the MSP on any
matroid, and on its strong form, claims that the constant is e. They also provide a Threshold Price
Algorithm (TPA) achieving an O(log ρ) utility-competitive
ratio on matroids of rank ρ. Better
√
algorithms have improved this ratio to O( log ρ) by Chakraborty and Lachish [11] and later to the
current best ratio of O(log log ρ) by Lachish [34] and independently by Feldman et al. [19].
The generalized secretary problem has also been studied on non-matroidal systems such as
knapsack [4], online matchings on graphs and hypergraphs [13, 33, 29] and LP packings [30].
Babaioff et al. [5] show that for general independence systems every algorithm on n elements must
be Ω(log n/ log log n) utility-competitive and Rubinstein [42] provides an O(log n log ρ) competitive
algorithm. Many works consider alternative objective functions, such as minimum sum of ranks
[1], time discounted variants [3], convex costs under knapsack type restrictions [6] and submodular
objectives [7, 18, 20]. Another rich line of research focuses on relaxing the random order condition
and the power of the adversary setting the weights. There are O(1) competitive algorithms for the
MSP on the random order and assignment model [44], on the adversarial order random assignment
model [41, 44] and on the free order model [25]. Non-uniform arrival orders have also been considered
[28]. Related to this line of research is the design of order-oblivious algorithms, which can sample
a constant fraction of the elements but afterwards, the arrival order may be arbitrary; and results
related to prophet inequality settings on which the weight of each element is a random variable
with known distribution but the arrival order is adversarial, see [32, 2, 15, 43].

1.1

Ordinal MSP versus Utility MSP

A common requirement for the mentioned algorithms for the MSP on general matroids is that
they require to use numerical weights: they all treat elements with similar weights more or less
equivalently. In contrast, in the definition of the classical secretary problem, the decisions made
by an algorithm only rely on the ordinal preferences between candidates. This is a very natural
condition as for many applications it is difficult to determine (for instance, via an interview) a
numerical weight representing each candidate, but it is often simple to compare any two of them.
For this reason we restrict our study to the ordinal MSP in which the decision maker can only
compare seen elements. This is, it can check which element is higher in an underlying hidden total
order ≻. In particular, the algorithm cannot really compute the weight of a set. However, matroids
1

An independence system is a pair (R, I) where R is finite, and I is a nonempty family of subsets of R that is
closed under inclusion. The sets in I are called independent sets.
2
A matroid is an independence system (R, I) satisfying the next augmentation property: whenever X, Y ∈ I, and
|X| < |Y |, there must be an element r ∈ Y \ X such that X + r ∈ I.

2

have the following extremely nice feature: it is possible to find a maximum weight independent set
using only ordinal information by greedily constructing an independent set using the order ≻. The
set OPT found this way is the unique lexicographically3 maximum independent of the matroid. So
it is quite natural to ask what can be done without numerical weights in the secretary setting. In
order to measure the performance of an algorithm we introduce three notions of competitiveness
for the ordinal MSP. We say that an algorithm is α ordinal-competitive if for every nonnegative
weight function compatible with the total order, the expected weight of the output independent set
ALG is at least 1/α the weight of OPT. It is α intersection-competitive if the expected fraction of
elements in OPT that is included into ALG is at least 1/α, and it is α probability-competitive if for
every element r ∈ OPT, the probability that r is included into ALG is at least 1/α. It is not hard
to see that any α ordinal-competitive algorithm is also α competitive in the classical (utility) sense
and also that any α probability-competitive algorithm is also α competitive in every other setting.
All the mentioned algorithms [5, 11, 34, 19] for the standard or utility MSP do not work in the ordinal model, and so the existence of an α-utility competitive algorithm does not imply the existence
of an α probability/intersection/ordinal competitive algorithm. To the authors’ knowledge the only
known algorithms for ordinal MSP on general matroids (apart from the trivial O(ρ) probabilitycompetitive that selects the top independent singleton using a classical secretary algorithm) are
Bateni et al.’s O(log2 ρ) ordinal-competitive algorithm [7] (which also works for submodular objective functions) and Soto’s variant of TPA [44] which is O(log ρ) ordinal-competitive.
Independently and simultaneously from this work, Hoefer and Kodric [23] study the ordinal
secretary problem obtaining constant ordinal-competitive algorithms for bipartite matching, general
packing LP and independent sets with bounded local independence number. They also show that
Feldman and Zenklusen’s reduction [20] from submodular to linear MSP works in the ordinal model.
The strong matroid secretary conjecture may hold even for the probability-competitive notion.
We note, however, that for some matroid classes the notion of competitiveness matters. In the
J-choice K-best secretary problem by Buchbinder et al. [10], one has to select J elements from
a randomly ordered stream getting profit only from the top K elements. In particular, every α
competitive algorithm for the ρ-choice ρ-best secretary problem that only uses ordinal information,
is an α intersection-competitive algorithm for uniform matroids of rank ρ. Chan et al. [12] show
that the best competitive ratio achievable by an algorithm that can only use ordinal information on
the 2-choice 2-best secretary problem is approximately 0.488628. In contrast, by using numerical
information one can achieve a higher competitive ratio of 0.492006 that also works for the sumof-weights objective function (i.e., for utility-competitiveness). Thus showing a gap between the
optimal probability ratio and the optimal utility ratio achievable on uniform matroids of rank 2.

1.2

MSP on specific matroids

An extensive amount of work has been done on the last decade on the MSP on specific matroid
classes including unitary [36, 16, 22, 8, 9], uniform [4, 31], transversal [5, 13, 33], graphic [5, 3, 33],
cographic [44], regular and MFMC [14], k-column sparse [44] and laminar matroids [24, 25, 39].
Even though the algorithms are stated for the utility MSP, many of the proofs work directly on
either the ordinal MSP under ordinal or even probability competitiveness. We include in Table 1
a summary of all known results together with the improved bounds obtained in this paper.
3

A set A = {a1 , . . . , ak } ⊆ R is lexicographically larger than a set B = {b1 , . . . , bk } ⊆ R of the same size, with
respect to the order ≻ on A ∪ B if ai ≻ bi for the first i on which ai and bi differ.

3

Matroid Class
Transversal
µ exch. gammoids
(type of hypermatching)
Matching matroids
µ exch. matroidal packings
Graphic
Hypergraphic
k-sparse matroids
k-framed matroids
Semiplanar gammoids
Laminar
Uniform U (n, ρ)
Cographic
Regular, MFMC

o:
u:

o:
o:

o:
p:
p:
o:
p:
o:

Previous guarantees
(u,o,p competitive)
16 [13], 8 [33], e [29]
O(µ2 ) [33], eµ [29]
16 [5], 3e [3], 2e [33]
ke [44]
√
177.77 [24], 3 3e ≈ 14.12 [25]
9.6 [39]
e [4] p
1 + O( 1/ρ)
3e [44]
9e [14]

New algorithms
p-guarantee
ref.
forb. size
e
Alg. 1
1
µµ/(µ−1)
Alg. 2
µ
4
µ

µ/(µ−1)

4
4
k k/(k−1)
k k/(k−1)
4/3
√ 4
3 3 ≈ 5.19615
p
1 + O( log ρ/ρ)
-

Alg.
Alg.
Alg,
Alg,
Alg.
Alg.
Alg.
Alg.

3
3
4
4
5
5
6
7

2
µ
2
2
k
k
4
3

Alg. 8

-

-

-

Table 1: State of the art competitive ratios for all known matroid classes, including our results.

1.3

Our results and techniques

We first formalize our new competitiveness notions for ordinal MSP and study their interrelations.
We say that a performance notion is stronger than another if any algorithm that is α competitive
for the former is also α competitive for the latter. Under this definition, we show that probability
is stronger than ordinal and intersection, and that ordinal is stronger than utility.
On the first part of our article we focus on a powerful technique to define strong algorithms for
the MSP on many classes of matroids. Informally (see the exact definition in Section 3), we say
that an algorithm has forbidden set of size k if it samples without selecting s ∼ Bin(n, p) elements
and the following condition holds. Suppose that an element r ∗ of OPT arrives in a position t > s
and let Rt be the set of elements that arrived on or before time t. For each time step i between
s + 1 and t − 1 there is a random set Fi of at most k forbidden elements such that if for every i, the
element arriving at time i is not forbidden (i 6∈ Fi ) then r ∗ is sure to be selected. The following is
the key lemma that shows why algorithms with small forbidden sets are useful for the MSP.
Lemma 1 (Key Lemma). By setting the right sampling probability p = p(k), every algorithm with
forbidden sets of size k is α(k) probability competitive, where
(
(1/e, e)
if k = 1,
(p(k), α(k)) =
1
k
(k− k−1 , k k−1 ) if k ≥ 2.
Obtaining algorithms with small forbidden sets is simple for many matroid classes. In fact, it is
easy to see that the variant of the standard classical secretary algorithm which samples s ∼ Bin(n, p)
elements and then selects the first element better than the best sampled element, has forbidden
sets of size 1. Suppose that the maximum element r ∗ arrives at time t > s and denote by x the
second best element among those arrived up to time t. If x does not arrive at any time between
s + 1 and t − 1 then for sure, x will be used as threshold and thus r ∗ will be selected. In the
4

above notation, all forbidden sets Fi are equal to the singleton {x}. Using the key lemma, by
setting p = 1/e, this algorithm is e competitive. We provide new algorithms that beat the state
of the art guarantees for transversal, graphic, k-sparse and laminar matroids. We also provide
new algorithms for other classes of matroids such as matching matroids, certain matroidal graph
packings (which generalize matching matroids), hypergraphic matroids, k-framed matroids (which
generalize k-sparse matroids), semiplanar gammoids
p and low exchangeability gammoids. As an
interesting side result, we revisit Kleinberg’s 1 + O( 1/ρ) ordinal-competitive algorithm. We show
that its probability-competitiveness is bounded
away from 1 and propose an algorithm that achieves
p
a probability-competitive ratio of 1 + O( log ρ/ρ). Our new results for specific classes of matroids
are summarized on Table 1, which, for completeness includes all matroid classes ever studied on
the MSP, even those for which we couldn’t improve the state of the art. In the references within
the table u, o and p stand for utility, ordinal and probability competitiveness respectively.
On the second part of this paper we obtain results for the ordinal MSP on general matroids.
Theorem 2. There exists a ln(2/e) intersection-competitive algorithm for the MSP.
Theorem 3. There exist an O(log log ρ) ordinal-competitive algorithm and an O(log ρ) probability
competitive algorithm for the MSP.
Even though Theorem 2 is attained by a very simple algorithm, we note that standard ideas such
as thresholding do not work for the intersection notion since elements outside OPT that are higher
than actual elements from OPT do not contribute to the objective. The algorithms mentioned
in Theorem 3 are based on the recent O(log log ρ) utility-competitive algorithm by Feldman et
al. [19]. Their algorithm samples a fraction of the elements so to classify most of the non-sampled
ones into h = O(log ρ) weight classes consisting on elements whose weights are off by at most a
factor of 2. They implement a clever random strategy to group consecutive weight classes together
into buckets, each one containing roughly the same random number of weight classes. On each
bucket they define a single random matroid with the property that if one picks an independent set
from each one of these matroids, their union is independent in the original one. Their algorithm
then selects a greedy independent set on each bucket matroid and output their union. Due to
the random bucketing, the expected number of elements selected on each weight class is at least
Ω(1/ log h) times the number of elements that OPT selects from the same class. This means that
the global algorithm is actually O(log h) = O(log log ρ) utility-competitive.
In the ordinal setting we cannot implement this idea in the same way, since basically we do not
have any weights. However, we can still partition the elements of the matroid into ordered layers.
The idea is to select a collection of thresholds obtained from the optimum of a sample, and use
them as separators to induce the layers. This motivates the definition of the Layered-MSP (see
Section 4.2). For both ordinal and probability competitiveness we provide a reduction from the
Layered-MSP to the ordinal MSP. For the ordinal notion, we select as thresholds a geometrically
decreasing subset of the sample optimum according to the value order, so we can partition the
matroid into h = O(log ρ) layers. For the probability notion we use all the elements of the sample
optimum as thresholds. The crucial result in this part is that our reduction allows to go from any
g(h) competitive algorithm for the Layered-MSP to a g(O(1+log h)) ordinal-competitive algorithm,
and to a g(O(h)) probability-competitive algorithm. In particular, by applying Feldman et al.’s
algorithm, interpreting these layers as weight classes, we get an O(log log ρ) ordinal-competitive
algorithm and an O(log ρ) probability-competitive algorithm for the original matroid.

5

1.4

Organization

In Section 2 we fix some notation and formally describe the performance guarantees for the ordinal
MSP, studying their relations. In Section 3 we prove our key lemma for algorithms with small
forbidden sets. We then devise simple algorithms for all the matroid classes mentioned in Table 1.
In Section 4 we describe our new algorithms for general matroids, and prove Theorems 2 and 3.
To keep the discussion clear and simple, we defer some of the proofs to the Appendix.

2

Preliminaries

Let M = (R, I, ≻) be a matroid with ground set R = {r 1 , r 2 , . . . , r n }, and ≻ a total order. We
call ≻ the value order and say that r 1 is the highest valued element, r 2 is the second one, and so
on, then r 1 ≻ r 2 ≻ · · · ≻ r n . By matroid properties, for every subset Q ⊆ R, there is a unique
lexicographically optimum base4 OPT(Q) obtained by applying the greedy algorithm in the order ≻,
over the set Q. We say that a nonnegative weight function w : E → R+ is compatible with the
value order if r i ≻ r j =⇒ w(r i ) ≥ w(r j ). Note that for every compatible weight function the set
OPT = OPT(E) is a maximum weight independent set. We reserve the use of superscripts k ∈ N
on a set Q to denote the subset of the highest min{k, |Q|} valued elements of Q. In particular Rk
and OPTk denote the set of the top k elements of the matroid and of OPT respectively. We also
reserve n and ρ to denote the number of elements of R and its rank respectively.
In the (utility/ordinal) MSP, the elements of a (nonnegatively weighted/totally ordered matroid)
are presented in uniform random order to an online algorithm that does not know a priori the
(weights/value order) of unrevealed elements. At any moment, the algorithm can (view the weight
of/compare in the total order) any pair of revealed element. When a new element r is presented,
the algorithm must decide whether to add r to the solution and this decision is permanent. The
algorithm must guarantee that the set of selected elements is at all times independent5 in the
matroid. The objective of the algorithm is to return a set ALG as close as OPT as possible
according to certain competitiveness metric.
To make notation lighter, we use + and − for the union and difference of a set with a single
element respectively. That is, Q+r −e = (Q∪{r})\{e}. The rank of a set S is the cardinality of its
bases, ρ(Q) = max{|I| : I ∈ I, I ⊆ Q}, and the span of Q is span(Q) = {r ∈ R : ρ(Q + r) = ρ(Q)}.
In matroids, OPT has the property of improving any subset in the following sense.
Lemma 4. Let Q ⊆ R. Then, OPT ∩ Q ⊆ OPT(Q).
Proof of Lemma 4. Let r = r k be an element of OPT ∩ Q. Since r k is selected by the Greedy
algorithm we have that r 6∈ span(Rk−1 ). But then r 6∈ span(Rk−1 ∩ Q) and so it is also selected by
the Greedy algorithm applied only on the set Q. Therefore, r ∈ OPT(Q).
Recall that the algorithm considered for the MSP have access to the elements in an online and
uniformly at random fashion. We denote by r1 the first element arriving, r2 the second, and so on.
In general, Rt = {r1 , r2 , . . . , rt } is the set of elements arriving up to time t.
4

A base of a set Q is a maximal independent subset X ⊆ Q.
For particular classes of matroids, we may assume that M is known beforehand by the algorithm, or alternatively
that it is discovered by the algorithm via an independence oracle that allows it to test any subset of revealed elements.
In any case, it is a standard assumption that the algorithm at least know the number of elements n in the matroid.
5

6

Utility competitiveness.
competitive if

An algorithm for the utility MSP returning a set ALG is α ≥ 1 utilityE[w(ALG)] ≥ w(OPT)/α.

2.1

(1)

Measures of competitiveness for the ordinal MSP

We introduce three measures of competitiveness or the ordinal MSP. Recall that the algorithm only
learns ordinal information about the elements but it cannot access numerical weights. In this sense,
they are closer to the classical secretary problem than the utility variant (for a discussion about
this aspect in the original secretary problem, see [21]).
Since the weight function remains completely hidden for the algorithm, the first measure of competitiveness we consider is the following. An algorithm is α ordinal-competitive if for every weight
function w compatible with the value order, condition (1) holds. An equivalent characterization of
competitiveness is obtained by the following lemma.
Lemma 5. An algorithm is α ≥ 1 ordinal-competitive if and only if for every k ∈ [n],
E|ALG ∩ Rk | ≥ E|OPT ∩ Rk |/α.

(2)

Proof. Consider an α ordinal-competitive algorithm returning a set ALG and let k ∈ [n]. Define
the weight function w(r) = 1 if r ∈ Rk and zero otherwise, which is compatible with the value
order. Then, E[|ALG ∩ Rk |] = E[w(ALG)] ≥ α1 w(OPT) = α1 |OPT ∩ Rk |. Now suppose that (2)
holds. Then, for any compatible function w, and defining w(r n+1 ) := 0,
E[w(ALG)] =

n
X
k=1

≥

n
X
k=1

(w(r k ) − w(r k+1 )) · E[|ALG ∩ Rk |]
(w(r k ) − w(r k+1 )) ·

1
1
E[|OPT ∩ Rk |] = E[w(OPT)].
α
α

In the second measure we consider, we want to make sure that every element of the optimum is
part of the output with large probability. We say that an algorithm is α ≥ 1 probability-competitive
if for every e ∈ OPT,
Pr(e ∈ ALG) ≥ 1/α.
(3)
Finally, in the third measure we want to maximize the number of elements in the optimum that
the algorithm outputs. We say an algorithm is α ≥ 1 intersection-competitive if
E[|OPT ∩ ALG|] ≥ |OPT|/α.

(4)

Relation between variants. The ordinal and probability measures are in fact stronger than the
standard utility notion. That is, any α ordinal/probability-competitive algorithm yields to an α
utility-competitive algorithm. Furthermore, the probability is the stronger of them all.
Lemma 6. If an algorithm is α ordinal-competitive then it is α utility-competitive. If an algorithm
is α probability-competitive then it is also α ordinal, utility and intersection-competitive.

7

Proof of Lemma 6. If an algorithm is α ordinal-competitive then by definition it is α utilitycompetitive. Now consider an α probability-competitive algorithmPreturning a set ALG. For
any k ∈ [n], we have E[|ALG ∩ Rk |] ≥ E[|ALG ∩ OPT ∩ Rk |] =
r∈OPT∩Rk Pr(r ∈ ALG) ≥
|OPT∩Rk |
.
α

which means that the algorithm is α ordinal-competitive, and therefore, it is also α
utility-competitive. To see that the algorithm is also α intersection-competitive we note that
E[|ALG ∩ OPT|] =

X

e∈OPT

Pr(e ∈ ALG) ≥

|OPT|
.
α

An algorithm for the utility variant, which recall is able to use the elements’ weights, may not
be adapted to the ordinal MSP, since in this model it can not use any weight information. In other
words, the existence of an α utility-competitive for a matroid (or matroid class) does not imply
the existence of an α-competitive algorithm for any of the other three measures. It is worth noting
that the intersection-competitive measure is incomparable with the other measures. It is not hard
to find fixed families of instances for which a given algorithm is almost 1 intersection-competitive
but has unbounded utility/ordinal/probability-competitiveness. There are also examples achieving
almost 1 ordinal-competitiveness but unbounded intersection-competitive ratio.

3

Improved algorithms for specific matroids

In this section we describe a powerful forbidden sets technique to analyze algorithms for the ordinal
MSP. Thanks to this technique we devise algorithms for many matroid classes previously studied in
the context of MSP and to other matroids that have not been studied in this context. Our results
improve upon the best known competitive ratios for almost all studied matroid classes. The only
classes in which we do not find an improvement are cographic matroids for which there is already a
3e probability-competitive algorithm [44], and regular-and-MFMC matroids for which there is a 9e
this section we briefly study uniform matroids,
ordinal-competitive algorithm [14]. At the end of p
for which Kleinberg’s algorithm [31] yields a 1 + O( 1/ρ) ordinal-competitive guarantee. We show
that the probability-competitiveness of Kleinberg’s algorithm
is at least 4/3 and we propose a
p
variant that achieves a slightly weaker ratio of 1 + O( log ρ/ρ) in the probability notion.

3.1

Forbidden sets technique

The following is the key definition that allows us to devise constant probability-competitive algorithms for specific classes of matroids. Recall that |R| = n, and for t ∈ [n], rt is the random element
arriving at time t, and Rt is the random set of elements arriving at or before time t.
Definition 7. An algorithm has forbidden sets of size k if it has the following properties.
1. (Correctness) The algorithm returns an independent set ALG.
2. (Sampling property) It chooses a sample size s at random from Bin(n, p) for some fixed
sampling probability p, and it does not accept any element from the first s arriving ones.
3. (k-forbidden property) For every triple (X, Y, r ∗ ) with Y ⊆ R, r ∗ ∈ OPT(Y ) and X ⊆
Y − r ∗ , one can define a set F(X, Y, r ∗ ) ⊆ X of at most k forbidden elements of X such that
the following condition holds. Let t ≥ s + 1 be a fixed time. If rt ∈ OPT(Rt ) and for every
j ∈ {s + 1, . . . , t − 1}, rj 6∈ F(Rj , Rt , rt ) then rt is selected by the algorithm.

8

To better understand the k-forbidden property suppose that a fixed element r ∗ ∈ OPT arrives
at step t ≥ s + 1, that is rt = r ∗ . Note that the set Rt−1 of elements arriving before rt is a
random subset of size t − 1 of R − rt , and no matter the choice of Rt−1 , r ∗ is always part of
OPT(Rt ) = OPT(Rt−1 + rt ). Inductively, for j = t − 1 down to j = 1, once Rj is specified, rj is a
uniform random element of Rj , and Rj−1 is defined as Rj − rj . Moreover, this choice is independent
of the previous random experiments (i.e., the choices of {rj+1 , . . . , rt−1 , Rt−1 }). The k-forbidden
property (3.) says that if for every j ∈ {s + 1, . . . , t − 1} element rj is not a forbidden element
in F(Rj , Rt , rt ) then r ∗ is guaranteed to be selected by the algorithm. Designing algorithms with
small forbidden sets is the key to achieve constant competitiveness as our key Lemma (that we
restate below) shows.
Lemma 1 (Key Lemma). By setting the right sampling probability p = p(k), every algorithm with
forbidden sets of size k is α(k) probability competitive, where
(
(1/e, e)
if k = 1,
(p(k), α(k)) =
k
1
(k− k−1 , k k−1 ) if k ≥ 2.
Proof. Fix an element r ∗ from OPT and condition on the realization of s ∼ Bin(n, p), on the time
t on which r ∗ = rt arrives and on the set Y = Rt ∋ rt of the first t elements arriving. Abbreviate
Pt (·) = Pr(·|rt = r ∗ , Rt = Y, s). By Lemma 4, r ∗ ∈ OPT(Rt ) and by the k-forbidden property,
Pt (r ∗ ∈ ALG) ≥ Pt (For all j ∈ {s + 1, . . . , t − 1}, rj ∈ Rj \ F(Rj , Y, r ∗ ))
t−1
t−1
Y j − k
Y
∗
Pr(rj ∈ Rj \ F(Rj , Y, r )) ≥
,
=
j
+
j=s+1

j=s+1

where x+ = max{0, x}. The equality above holds because of the independence of the random
experiments defining iteratively rt−1 , rt−2 , down to rs+1 as mentioned before the statement of this
lemma. By removing the initial conditioning we get
n
1 X
Pr(r ∈ ALG) ≥ Es∼Bin(n,p)
n
∗

t−1
Y

t=s+1 j=s+1



k
1−
j



.

(5)

+

To compute the right hand side we use the following auxiliary process. Suppose that n people
participate in a game. Each player x arrives at a time τ (x) chosen uniformly at random from the
interval [0, 1]. Each person arriving after time p selects a subset of k partners from the set of people
arriving before them, without knowing their actual arrival times (if less than k people have arrived
before her, then all of them are chosen as partners). A player wins if she arrives after time p and
every one of her partners arrived before time p. Since the arrival times are equally distributed
and the event that two people arrive at the same time has zero probability the arrival order is
uniform among all possible permutations. Furthermore, the number of people arriving before time
p distributes as Bin(n, p). Using these facts, the probability that a given person x wins is exactly
the right hand side of (5). But we can also compute this probability using its arrival time τ (x) as
Z

1
p

Pr( all partners of x arrived before time p | τ (x) = τ ) dτ ≥
9

Z

1
p

(p/τ )k dτ,

which holds since the arrival time of each partner of x is a uniform random variable in [0, τ ], and
conditioned on τ , each partner arrives before time p with probability p/τ . Since x may have less
than k partners, we don’t necessarily have equality. We conclude that for every r ∗ ∈ OPT,

Z 1
−p ln(p), if k = 1,
k
∗
(p/τ ) dτ = p − pk
Pr(r ∈ ALG) ≥

p
,
if k ≥ 2.
k−1
By optimizing the value of p as a function of k, we obtain that the probability of r ∗ ∈ ALG is
1/α(k), with α(k) as in the statement of the lemma and the probability achieving it is p = p(k).

The idea of analyzing an algorithm as a series of stochastically independent experiments which
defines the reverse arrival sequence appears very early in the history of the secretary problem. As
mentioned in the introduction, one can prove that the algorithm for the classical secretary algorithm
that samples s ∼ Bin(n, p(1)) elements and then selects the first element better than all the sampled
ones is e probability-competitive showing that it has forbidden sets of size 1. In our notation, for
each (X, Y, r ∗ ) with r ∗ the maximum element of Y and X ⊆ Y − r ∗ , define the forbidden set
F(X, Y, r ∗ ) as the singleton OPT(X). The 1-forbidden condition states that if the element rt
arriving at time t is a record (it is in OPT(Rt )), and if for every time j ∈ {s + 1, . . . , t − 1},
rj 6∈ OPT(Rj ) (i.e., the j-th arriving element is not a record), then rt will be chosen by the
algorithm. Since all forbidden sets have size at most 1, setting the sampling probability to be
p(1) = 1/e guarantees the probability-competitive ratio of α(1) = e.
Kesselheim et al.’s algorithm for online bipartite matching [29] uses a technique very similar to
that in the previous lemma to compute the expected weight contribution of the k-th arriving vertex,
which is enough to prove asymptotically e + O(1/n) utility-competitiveness for online bipartite
matchings. In fact, for transversal matroids, this yields to an e + O(1/n) ordinal-competitive
algorithm. But their analysis does not imply any guarantee on the probability notion. In the next
section we show by using a different analysis, that their algorithm has forbidden sets of size 1 and
so it is actually e probability-competitive (always, not just asymptotically).
It turns out that many classes of matroids behave very similarly to transversal matroids in the
following sense. A set X is independent on a given matroid if and only if each element r ∈ X can
be mapped to an object (e.g., an edge covering r, a path ending in r, a subgraph covering r, etc.)
r̃ such that the set X̃ = {r̃ : r ∈ X} satisfies a combinatorial property (e.g., a matching covering
X, a collection of edge/node disjoint paths connecting X with some source, a collection of disjoint
subgraphs covering X). We call X̃ a witness for the independence of X. A set X may have multiple
witnesses, but we will always assume that there is a canonical witness, witness(X), that can be
computed by the algorithm and furthermore, the choice of the witness cannot depend on the set
of elements seen so far nor on its arrival order. The fact that the witnesses do not depend on the
arrival order makes them amenable to the analysis by the reverse arrival sequence analysis above,
which in turn, will help us to devise algorithms with constant-size forbidden sets.

3.2

Transversal matroids and Gammoids

Transversal matroids. Let G = (L ∪ R, F ) be a bipartite graph with color classes L and R, where
the elements of R are called the terminals of G. The transversal matroid T [G] associated to G is
the matroid with ground set R whose independent sets are those X ⊆ R that can be covered by a
10

matching in G. We call G the transversal presentation of T [G].
Gammoids. Let G = (V, E) be a digraph and two subsets S, R ⊆ V called sources and terminals
respectively, which do not need to be disjoint. The gammoid Γ(G, S, R) is the matroid over the
terminals where X ⊆ R is independent if X is linked to S, that is, if there are node-disjoint directed
paths starting from S and ending on each element of X. We say that (G, S, R) is the gammoid
presentation of the matroid. Note that transversal matroids are gammoids by declaring all the nonterminals as sources and directing the arcs in the transversal presentation from sources to terminals.
Transversal and Gammoid MSP. In the Transversal MSP, a transversal presentation G for an
unknown ordered matroid M = T [G] is either revealed at the beginning of the process, or it is
revealed online in the following way. Initially, the algorithm only knows the number of terminals.
Terminals arrive in random order and whenever r ∈ R arrives, it reveals its ordinal value information
and the set of its neighbors in L. In the gammoid MSP, a gammoid presentation (G, S, R) for an
unknown gammoid is either revealed at the beginning or it is revealed online as elements from
R arrive: when a terminal r ∈ R arrives all possible S-r paths are revealed. At that time the
algorithm has access to the subgraph Gt ⊆ G only containing the arcs belonging to every possible
S-Rt path and can test whether a vertex is in S or not.
Most of the known algorithms for transversal MSP [5, 13, 33] work with ordinal information.
The best algorithm so far, by Kesselheim et al. [29] achieves an asymptotically optimal utilitycompetitive ratio of e + O(1/n) for the more general (non-matroidal) vertex-at-a-time bipartite
online matching problem, in which edges incident to the same arriving vertex may have different
weights and the objective is to select a matching of maximum total weight. For the specific case
of transversal matroid this algorithm can be implemented in the ordinal model, meaning that is
e + O(1/n) ordinal-competitive. Interestingly, for the broader bipartite matchings case, Kesselheim’s algorithm does not work in the ordinal model, but the previous algorithm by Korula and
Pál [33] does, achieving 8 ordinal-competitiveness. A recent result by Hoefer and Kodric [23] improves this factor to 2e ordinal-competiive for bipartite matchings.
Exchangeability parameter for gammoids. Let us define a parameter to control the competitiveness
of our algorithm for the gammoid MSP. Let X be an independent set and let Q be a path linking
a terminal r ∈ R \ X outside X to S. The exchangeability µ of the presentation (G, S, R) is the
maximum number of paths in PX that Q intersects. The intuition behind is the following: in order
to include Q into PX while keeping disjointness we have to remove or exchange at least µ paths
from PX . For instance, if we define the diameter d of the gammoid presentation as the maximum
number of nodes in any source-terminal path, then µ is at most d. If furthermore the terminals are
sinks, that is out-degree 0, then µ is at most d − 1, since paths ending at different terminals cannot
intersect on a terminal.
Remark 8. This is the case for transversal matroids: their diameter in the gammoid presentation
is 2 and their exchangeability is 1. For our results, we assume the algorithm also knows an upper
bound µ for the exchangeability parameter, and in this case we call the problem µ-gammoid MSP
or bounded exchangeability gammoid MSP.
The µ-gammoid MSP problem is a special case of the (non-matroidal) hypergraph vertex-at-atime matching (HVM) with edges of size at most µ + 1 studied by Korula and Pál [33] and later by
11

Kesselheim et al.’s [29] online hypermatching problem (see the discussion in those papers for precise
definitions). They achieve O(µ2 ) and eµ utility-competitiveness respectively. Below we propose an
algorithm for the µ-gammoid MSP that has forbidden sets of size µ. Provided we know µ upfront
we get an α(µ) probability-competitive algorithm. Note that for µ ≥ 2, α(µ) = µ1+1/(µ−1) < eµ,
so our guarantee strictly improves on that of previous algorithms for HVM and hypermatching, on
the special case of µ-gammoids.
Our algorithms. We use the convention that for every vertex v covered by some matching M , M (v)
denotes the vertex matched with v in M . Furthermore, for every independent set X ⊆ R, we select
canonically a witness matching MX := witness(X) that covers X. In the case of gammoids, for
any set P of node-disjoint paths linking some set X to S, and for every v ∈ X, P(v) denotes the
unique path in P linking v to S. We also say that P covers a vertex u if u is in the union of the
vertices of all paths in P. Furthermore, for every independent set X ⊆ R, we canonically select
a fixed collection of node-disjoint S-X directed paths PX := witness(X) linking X to S, and we
assume that this choice does not depend on the entire graph but only on the minimum subgraph
containing all arcs in every S-X path. We also recall that on step i, Ri = {r1 , . . . , ri } denotes
the set of revealed terminals and Gi denotes the subgraph of the presentation currently revealed.
Algorithm 1 for transversal matroids.

Algorithm 2 for µ-bounded gammoids.

Input: Presentation of a transversal matroid T [G] Input: Presentation of a gammoid Γ := Γ(G, S, R)
whose terminals arrive in random order.
whose terminals arrive in random order.
⊲M and ALG are the currently chosen matching
⊲P and ALG are the currently chosen collection
and right vertices respectively.
of node-disjoint paths and terminals selected respectively.
1: ALG ← ∅, s ← Bin(n, p), M ← ∅
1: ALG ← ∅, s ← Bin(n, p), P ← ∅.
2: for i = s + 1 to n do
2: for i = s + 1 to n do
3:
if ri ∈ OPT(Ri ) and ℓi := MOPT(Ri ) (ri ) is 3:
if ri ∈ OPT(Ri ) and no vertex in the path
not covered by M then
POPT(Ri ) (ri ) is covered by P then
4:
ALG ← ALG + ri , M ← M ∪ {ℓi ri }
4:
ALG ← ALG+ri , P ← P∪{POPT(Ri ) (ri )}
5: Return ALG.

5: Return ALG.

The algorithms above can compute OPT(Ri ) without knowing the terminal weights, by just
using the greedy algorithm. This requires that one is able to check independence algorithmically
in each case. Indeed, for the transversal MSP algorithm, a set X ⊆ Ri is independent if and only if
the maximum cardinality matching on Gi [NG (X) ∪ X] has size |X|. In the case of gammoids, one
can check if X ⊆ Ri is independent, by a standard reduction to a flow problem on Gi .
Theorem 9. Algorithm 2 has forbidden sets of size equal to the exchangeability µ of the gammoid
presentation. If µ is known, we can set p = p(µ) to get an α(µ) probability-competitive algorithm.
Proof. By construction, the set P contains node-disjoint paths covering ALG at every time step,
hence the algorithm is correct. The sampling condition is also satisfied by design. Let r ∗ ∈ OPT(Y )
where Y is a fixed set of terminals of size t ≥ s + 1, and suppose that Rt = Y and rt = r ∗ . Note
that rt is selected by the algorithm if all vertices in the path POPT(Rt ) (rt ) are not covered by the
collection P prior to that iteration. In other words, by defining the forbidden sets to be
F(X, Y, r ∗ ) = {v ∈ OPT(X) : POPT(X) (v) intersects POPT(Y ) (r ∗ )},
12

the element rt is selected if rj 6∈ F(Rj , Rt , rt ) for all j ∈ {s + 1, . . . , t − 1}. By definition, each
forbidden set has size at most µ.
Algorithm 1 is essentially Algorithm 2 applied over the gammoid presentation of the transversal
matroid T [G]. Together with Remark 8, it follows the result for the transversal MSP.
Theorem 10. Algorithm 1 has forbidden sets of size 1, and therefore, by choosing p = 1/e, it is
an (optimal) e probability-competitive for transversal matroids.
We remark that every constant utility-competitive algorithm so far for transversal MSP requires to learn a bipartite presentation online. It is an open problem to find constant competitive
algorithms for transversal matroids that only access the matroid via an independence oracle.

3.3

Matching Matroids and Matroidal Graph Packings

Matroidal graph packings. Let H be a finite set of graphs. An H-packing of a host graph G = (V, E)
is a collection Q = {Hi }i=1...k of node-disjoint subgraphs of G such that each H ∈ Q is isomorphic
to some graph in H. A vertex in G is said to be covered by Q if it belongs to some graph of Q.
Let R ⊆ V be a set of vertices called terminals and consider the independence system M(R, G, H)
over R whose independent sets are all X ⊆ R for which there is an H-packing covering X in G. We
say that H is matroidal if M(V (G), G, H) defines a matroid for every graph G. Note that in this
case, if M(R, G, H) is the restriction of M(V (G), G, H) to a subset R, then it is also a matroid.
We call every such M(R, G, H) a graph packing matroid.
Matroidal families. For an extensive treatment see Loebl and Poljak [37], Janata [27] and the
references therein. In the following examples, Kn denotes the complete graph on n vertices and
Sn denotes the star with n legs. If H = {K1 } then M(V, G, H) is the free matroid over V where
all sets are independent. If H = {K2 } then M(V, G, H) is the matching matroid of G, whose
independent sets are all vertex sets that can be covered by a matching. If for some k the family
H = {S1 , S2 , . . . , Sk } is a sequential sets of stars, then M(V, G, H) is matroidal. It is, in fact, the
matroid union of many matching matroids. The family M(V, G, H) is also matroidal if H = {K2 , H}
where H is either a factor-critical graph or a 1-propeller.6 For most known matroidal classes there
are polynomial time algorithms available to check independence. This is the case for all classes
above. Observe that transversal matroids are instances of matching matroids restricted to one side
of the bipartition of the host graph.
As we did for gammoids, we also define an exchangeability parameter µ to control the competitiveness of our algorithm. Consider an H-packing Q of G, and a subgraph H ⊆ G from the class
H covering a terminal r ∈ R that is not covered by Q. The exchangeability µ of M(R, G, H) is the
maximum number of terminals over all such Q and H that would become uncovered if we removed
all graphs from Q that intersect H, namely,




X
µ := max
|V (H ′ ) ∩ R| : H covers a terminal not covered by Q .
 ′

′
H ∈Q : V (H)∩V (H )6=∅

6
A factor-critical graph is one such that H − x admits a perfect matching for all x ∈ V (H). A 1-propeller is a
graph having a leaf r, and a vertex c such that for every x ∈ V (H) − c, H − x admits a perfect matching.

13

This parameter may be complicated to compute but there is a simple upper bound: let h be the
maximum number of vertices of a graph from H. Then the worst possible situation occurs when
Q contains only graphs of size h, and H is also a graph of size h intersecting every graph in Q
on exactly one vertex (different from r). In this case, all graphs from Q must be removed, so the
number of newly uncovered vertices becomes h · (h − 1). This means that µ ≤ h(h − 1).
In the H-Packing MSP, the algorithm receives a collection H of graphs. A host graph G = (V, E)
with terminals R ⊆ V is either revealed at the beginning or it is revealed online as elements from
R arrive: when a terminal r ∈ R arrives, all possible edges that belong to a graph H ⊆ G with
r ∈ V (H) with H ∈ H (via isomorphism) are revealed. More precisely, let Rt denote the set of
terminals revealed up to time t. At that time the algorithm has access to the subgraph Gt ⊆ G
induced by all vertices belonging to every possible subgraph H ⊆ G, with H ∈ H that intersects
Rt . The algorithm can also test whether a vertex is a terminal or not. We also assume that an
upper bound µ for the exchangeability parameter is available, and in this case we call the problem
bounded H-packing MSP. Analogously to previous sections, for every independent X we select a
canonical packing QX := witness(X) that does not depend on the arrival order.
In the description of the algorithm we use the convention that for every H-packing Q of a set
X, and for every v ∈ V covered by Q, Q(v) denotes the unique graph in Q covering v. We also
recall that on step i, Ri = {r1 , . . . , ri } denotes the set of revealed terminals and Gi denotes the
subgraph of the presentation currently revealed.
Algorithm 3 for µ bounded H-packing matroids.

Input: A matroidal family H and a host graph G = (V, E) whose terminals R ⊆ V arrive in random order.
⊲ Q and ALG are the currently chosen H-packing and terminals selected respectively.
1: ALG ← ∅, s ← Bin(n, p), Q ← ∅.
2: for i = s + 1 to n do
3:
if ri ∈ OPT(Ri ) and ri is already covered by Q. then
4:
ALG ← ALG + ri .
5:
else if ri ∈ OPT(Ri ) and Q ∪ {QOPT(Ri ) (ri )} is an H-packing. then
6:
ALG ← ALG + ri , Q ← Q ∪ {QOPT(Ri ) (ri )}.
7: Return ALG.

The algorithm can compute OPT(Ri ) without knowing the terminal weights, by applying the
greedy algorithm for M(R, G, H).
Theorem 11. Algorithm 3 has forbidden sets of size equal to the exchangeability µ of the Hpresentation. If µ is known beforehand, we can set p = p(µ) to obtain an α(µ) probabilitycompetitive algorithm for µ-bounded graph packing matroids.
Proof. Correctness and the sampling condition for forbidden sets are satisfied by design. Now let
r ∗ ∈ OPT(Y ) where Y is a fixed set of terminals of size t ≥ s + 1, and suppose that Rt = Y and
rt = r ∗ . Terminal rt is selected by the algorithm if either Q already covers it on arrival, or if all
vertices in the graph QOPT(Rt ) (rt ) were not covered by graphs in Q prior to that iteration.
In any case by defining as forbidden sets
F(X, Y, r ∗ ) = {v ∈ OPT(X) : V (QOPT(X) (v)) intersects V (QOPT(Y ) (r ∗ )) \ {r ∗ }},
we have that rt is selected if rj 6∈ F(Rj , Rt , rt ) for all j ∈ {s + 1, . . . , t − 1}. By definition, each
forbidden set has size at most µ.
14

We remark that the competitiveness achievable by an algorithm heavily depends on the way the
matroid is presented. For instance, consider a matching matroid M with host graph G = (V, E).
Note that the exchangeability of this matroid is µ ≤ 2(2 − 1) = 2. If the graph is presented online
then we can use the previous algorithm to obtain an α(2) = 4 probability-competitive algorithm.
If on the other hand the graph is presented upfront, then we can use the fact that every matching
matroid is transversal [17] to construct a transversal presentation of M and then apply our e
probability-competitive algorithm using that presentation.

3.4

Graphic and Hypergraphic Matroids

Graphic and hypergraphic matroids. The graphic matroid M[G] = (R, I) associated to a graph
G = (V, R) is the one whose independent sets are all the subsets of edges X ⊆ R such that (V, X)
is a forest. The hypergraphic matroid M[G] associated to a hypergraph G = (V, R), whose edges
may be incident to any number of vertices (if all the edges have size 1 or 2 we are back in the
graphic case), is the matroid over R whose independent sets X ⊆ R are those, for which one
 can
canonically choose for every r ∈ X an edge denoted by edge(r, X) = u(r)v(r) in KV = (V, V2 ) with
both endpoints in r in such a way that all edge(r, X), for r ∈ X are different, and the collection
edge(X) = {edge(r, X) : r ∈ X} is a forest [38].
One can check that the hypergraphic matroid M[G] = (R, I) is the matroid induced from the
graphic matroid M[KV ] via the bipartite graph (R ∪ V2 , Ẽ) with ef ∈ Ẽ if f ⊆ e. In other words,
X is independent in the hypergraphic matroid M[G] if edge(X) is independent in the graphic
matroid M[KV ]. Moreover, if G is already a graph, edge(X) = X and edge(r, X) = r for all r ∈ X.
In the graphic MSP /hypergraphic MSP we assume that the underlying graph/hypergraph G
of a matroid M[G] is either revealed at the beginning or revealed online in the natural way: we
learn edges as they arrive. Let X ⊆ R be an independent set. By orienting each connected component of the forest edge(X) from an arbitrary root, we obtain a canonical orientation arc(X) of
edge(X) (for convenience, we denote by arc(e, X) the oriented version of edge(e, X)) with indegree
deg−
arc(X) (v) ≤ 1 for every vertex v. The converse is almost true in the following sense. If A is

a set of arcs (maybe including loops) such that deg−
A (v) ≤ 1 for every vertex then the underlying
graph is not necessarily a forest in KV , but a pseudoforest: every connected component contains
at most 1 cycle, which is directed. In fact, the edge sets of pseudoforest of a given graph J are
exactly the independent set of the so called bicircular matroid of J. This matroid is transversal
with presentation H, where V (H) = V (J) ∪ E(J) and ve ∈ E(H) if and only if e is incident to v.
This is the starting point for our algorithm for graphic matroids.

The algorithm. The plan is to only consider edges that belong to the current optimum. Furthermore,
if we select an edge, then we orient it and include it into an arc set A with the property that each
vertex has maximum in-degree 1. Instead of using a random orientation (as in the algorithms by
Korula and Pál [33] or Soto [44]), at every step we use the canonical orientation of the current
optimum forest. In order to avoid closing a cycle we also impose that an arc (u, v) can not be
−
added to A if deg−
A (u) = 1 or degA (v) = 1. The same algorithm works on hypergraphic matroids if
we replace each independent set X on the hypergraphic matroid by its associated forest edge(X).
We also recall that on step i, Ri = {r1 , . . . , ri } denotes the set of revealed edges. The algorithm is
fully described below.

15

Algorithm 4 for graphic or hypergraphic matroids.
Input: A hypergraphic matroid M[G] with underlying hypergraph G = (V, R), whose edges arrive in
random order.
⊲ ALG and A are the currently selected independent set and the orientation of its associated forest.
1: ALG ← ∅, s ← Bin(n, p), A ← ∅.
2: for i = s + 1 to n do
3:
if ri ∈ OPT(Ri ) then
4:
Let ai = (ui , vi ) = arc(ri , OPT(Ri )) be the canonical orientation of edge(ri , OPT(Ri )).
−
5:
if deg−
A (ui ) = 0 = degA (vi ) then
6:
ALG ← ALG + ri , A ← A + ai
7: Return ALG.

Theorem 12. Algorithm 4 has forbidden sets of size 2. By setting p = p(2) = 1/2, we get an
α(2) = 4 probability-competitive algorithm for both graphic and hypergraphic matroids.
Proof. We first prove that the edge set Â obtained from A by removing its orientation is acyclic.
Suppose by contradiction that at the end of some step i, A contains for the first time a set C such
that its unoriented version Ĉ is an undirected cycle. Since this is the first time a cycle appears, ri
must be selected and ai = (ui , vi ) must be contained in C. Since ai is included in A, we know that
−
after its inclusion, deg−
A (vi ) = degC (vi ) = 1 (before its inclusion, the indegree of vi was 0) and that
−
+
−
deg−
A (ui ) = degC (ui ) = 0. But since Ĉ is a cycle the outdegree of ui is degC (ui ) = 2− degC (ui ) = 2.
But then, there must be another vertex x in C with indegree 2. This cannot happen because at
every moment the indegree of each vertex is at most 1.
The proof above guarantees correctness of the algorithm: for the graphic case Â = ALG and
for the hypergraphic case, each edge ri of ALG is mapped to edge(ri , OPT(Ri )) ∈ Â which form a
forest. In both cases we conclude ALG is independent.
Since the sampling condition is satisfied by design, we only need to prove the 2-forbidden
condition. Let r ∗ ∈ OPT(Y ) where Y is an arbitrary set of t ≥ s + 1 edges, and suppose that
Rt = Y and rt = r ∗ . The algorithm would then define an arc at = (ut , vt ) and will proceed to add
rt to ALG provided that no arc aj = (uj , vj ) considered before has head vj equal to ut or vt . In
other words, by defining
n
o
arc(f,OPT(X)) is not oriented
F(X, Y, r ∗ ) = f ∈ OPT(X) : towards
∗
any endpoint of edge(r ,OPT(Y ))

then rt is selected if rj 6∈ F(Rj , Rt , rt ) for all j ∈ {s + 1, . . . , t − 1}. Moreover, since each arc set
arc(OPT(X)) = {arc(f, OPT(X)) : f ∈ OPT(X)} has maximum indegree 1, there are at most 2
arcs in arc(OPT(X)) oriented towards an endpoint of edge(r ∗ , OPT(Y )). So each forbidden set has
size at most 2.

3.5

Column Sparse Representable Matroids and Multi-Framed matroids

Column sparse matroids. An interesting way to generalize graphic matroids is via their matrix
representation. We say that a matroid M is represented by a m × n matrix M with coefficients in
a field F if we can bijectively map the elements of its ground set to the columns of M in such a way
that the independent sets of M are in correspondence with the sets of columns that are linearly
independent in Fm . Graphic matroids are representable by their adjacency matrix interpreted in
GF (2). In fact they can be represented in any field. Matroids that have this property are called
16

regular. Note that each graphic matroid is representable by a very sparse matroid: each column
has only 2 non-zero elements. Following [44] we say that a matroid is k column sparse representable
if it admits a representation whose columns have at most k nonzero entries each. These matroids
include many known classes such as graphic matroids (k = 2), rigidity matroids [47] on dimension
d (k = 2d) and more generally matroids arising from rigidity theory from d-uniform hypergraphs.
These matroids are called (k, ℓ)-sparse matroids (where 0 ≤ ℓ ≤ kd − 1), and they are, using our
notation, kd column sparse [45]. Interesting cases include generic bar-joint framework rigidity in the
plane [35], which are characterized by (2, 3)-sparse matroids in dimension d = 2 (they are 4 column

sparse) and generic body-bar framework rigidity in Rd which are characterized by ( d+1
, d+1
)2
2
d+1
sparse matroids [46] (they are d 2 column sparse).
Let M be a matroid with k sparse representation M and let X be an independent set of columns.
It is easy to show (see e.g., [44]) that we can select one nonzero coordinate from each column in
X such that no two selected entries lie on the same row. In other words, each independent set in
M is also independent in the transversal matroid whose bipartite representations has color classes
the rows and columns of M and where a column i is connected to a row j if entry Mij is nonzero.
Even though the converse is not true, we can use the intuition obtained from graphic matroids to
extend the algorithm to k column sparse representable matroids with only few changes. Instead of
doing that, we are going to further generalize this class of matroids in a different direction.
Multiframed matroids. A matroid M is called a frame matroid [48] if it can be extended to a
second matroid M′ (i.e. M is a restriction of M′ ) which possesses a frame B, that is, a base such
that every element of M is spanned by at most 2 elements of B. For instance, take a graphic
matroid M[G] and consider the graph H = (V (G) + v0 , E(G) ∪ {v0 v : v ∈ V (G)} where v0 is
a new vertex. Then, M[H] is an extension of M[G] containing the star centered at v0 as basis
B := δH (v0 ) = {v0 v : v ∈ V (G)}. Since every edge uv in G is spanned by the set {v0 u, v0 v} of (at
most) 2 elements, we conclude that B is a frame for M[G]. We define a new class of matroids,
called multiframed of k-framed matroids, in a natural way. A matroid M = (R, I) is a k-framed
matroid if it admits an extension MB = (R′ , I) having a k-frame B, i.e., a base such that each
element of M is spanned by at most k elements of B. Without loss of generality we assume that
B ∩ R = ∅ (by adding parallel elements) and R′ = B ∪ R. In other words, MB is obtained by
adjoining the k-frame B to the original matroid M. Observe that if M is represented by a k
column sparse matrix M , then the matrix [I|M ] obtained by adjoining an identity (in the field F)
represents an extension MB of M where the columns of I form a base B such that each column in
M is spanned by at most k elements from B (exactly those elements associated to the k nonzero
rows of the column). This means that k-framed matroids generalizes k column sparse matroids.
This generalization is strict since there are frame matroids that are nonrepresentable.
We define the k-framed MSP as the variant of the MSP in which the k-framed matroid M,
and its extension MB is either fully known beforehand or we simply have access to B and an
independence oracle for MB (in the case of k column sparse matroid it is enough to receive the
columns of the representation in an online fashion).
We need some notation. For every r in the ground set R, we define the set C(B, r) = {y ∈
B : B +r −y is independent} which is also the minimal subset of B spanning r. It is easy to see that
C(B, r) + r is the unique circuit in B + r, often called the fundamental circuit of r with respect to
the base B in MB . Define also for each y ∈ B, the set K(B, y) = {r ∈ R : B +r−y is independent}.
It is easy to see that K(B, y) + y is the unique cocircuit inside R + y in the matroid MB , often
17

called the fundamental cocircuit of y with respect to the base B. Observe that by definition,
r ∈ K(B, y) ⇐⇒ y ∈ C(B, r). Furthermore, by definition of k-framed matroids, C(B, r) has at
most k elements. Before presenting the algorithm we need the following result.
Lemma 13. Let X be an independent set of a k-framed matroid M with k-frame B. There is a
(canonical) injection πX : X → B such that B + x − πX (x) is independent for all x ∈ X.
Proof. Extend X to a base X ′ of M′ . By the strong basis exchange axiom there is a bijection
π : X ′ → B such that B + x − π(x) is a base for all x ∈ X ′ . The restriction of π to X yields the
desired injection.
Algorithm 5 for k-framed matroids.
Input: A k-frame matroid M, with independence oracle access to MB and to B. The elements of M arrive
in random order.
⊲ ALG is the set currently selected and B ′ is the set of elements of the frame B that have been marked.
1: ALG ← ∅, s ← Bin(n, p), B ′ ← ∅.
2: for i = s + 1 to n do
3:
if ri ∈ OPT(Ri ) and C(B, ri ) ∩ B ′ = ∅ then
4:
ALG ← ALG + ri , B ′ ← B ′ + πOP T (Ri ) (ri )
5: Return ALG.

Theorem 14. Algorithm 5 has forbidden sets of size k. By setting p = p(k), we get an α(k)
probability-competitive algorithm for k-framed matroids.
Proof. Suppose that the algorithm is not correct, and let Z = {ri(1) , ri(2) , . . . , ri(ℓ) } be a circuit in
ALG with s + 1 ≤ i(1) ≤ i(2) ≤ · · · ≤ i(ℓ). When ri(1) arrived, y := πOPT(Ri(1) ) (ri(1) ) ∈ C(B, ri(1) )
was marked. Furthermore, our algorithm guarantees that for every element ri ∈ ALG with i > i(1),
y 6∈ C(B, ri ). In particular, y ∈ C(B, ri(j) ) ⇐⇒ j = 1, or equivalently, K(B, y) ∩ Z = {ri(1) }. But
this implies that the circuit Z and the cocircuit K := K(B, y) + y intersect only in one element,
which cannot happen in a matroid. Therefore, the algorithm is correct.
Since the sampling condition is satisfied by design, we only need to prove the k-forbidden
condition. Let r ∗ ∈ OPT(Y ) where Y is an arbitrary set of t ≥ s + 1 elements, and suppose that
Rt = Y and rt = r ∗ . The algorithm accepts r ∗ if and only if no element of C(B, rt ) was marked
before. Let y ∈ C(B, rt ) be an arbitrary element. A sufficient condition for y not being marked at
step j is that πOPT(Rj ) (rj ) 6= y. Therefore, if we define the forbidden sets
F(X, Y, r ∗ ) = {f ∈ OPT(X) : πOPT(X) (f ) ∈ C(B, r ∗ )}
it is clear that rt is selected if rj 6∈ F(Rj , Rt , r ∗ ) for all j ∈ {s + 1, . . . , t − 1}. Moreover, since
πOPT(X) is injective we conclude that |F(X, Y, r ∗ )| ≤ |C(B, r ∗ )| ≤ k.

3.6

Laminar Matroids and Semiplanar Gammoids

Arc-capacitated Gammoids. In this section we define special classes of gammoids amenable for
our techniques. An arc-capacitated gammoid (ACG) M[N ] is defined by a directed network N =
(G, s, R, c) where G = (V, E) is a digraph, s ∈ V is a single source, R ⊆ V \ {s} is a collection
of terminals and c : E → Z+ is a strictly positive integer capacity function on the arcs of G. The
18

ground set of M[N ] is R and every set J ⊆ R is independent if and only if there exist an s-R flow
on N satisfying the capacity constraints on the arcs and where each j ∈ J receives one unit of flow.
Without loss of generality we assume that every terminal is reachable from s via a directed path.
It is easy to see that ACGs are equivalent to gammoids without loops, but they are more closely
related to transportation or distribution applications.
A semiplanar gammoid is an ACG whose digraph G admits a semiplanar drawing, which is a
planar drawing where all terminals are on the x-axis, the source node is on the positive y-axis, and
the rest of the graph (arcs and nodes) are strictly above the x-axis, in a way that they do not touch
the infinite ray starting upwards from the source node. It is easy to see that G admits a semiplanar
drawing if and only if it is planar and all the terminals and the source are contained in the same
face (which could be a cycle, a tree or a pseudoforest).
Laminar Matroids. An important example of semiplanar gammoids are laminar matroids. A
collection L of non-empty subsets of a finite set of terminals R is called laminar if for every
L, H ∈ L, L ∩ H ∈ {L, H, ∅}. The laminar matroid M[R, L, c], where L is a laminar family over R
and c : L → Z+ is a positive integer capacity function on the sets of L, is the matroid with ground
set R and whose independent sets are those X ⊆ R for which the number of elements that X
contains in any set of the laminar family does not exceed its capacity, i.e. |X ∩ L| ≤ c(L). Observe
that, since c is positive, every singleton is independent. Furthermore, without loss of generality we
assume that R ∈ L (with c(R) equal to the rank of the matroid) and that all singletons are in L
(with c({r}) = 1 for each r ∈ R). Adding those sets does not destroy laminarity.
The Hasse diagram of the containment order of L forms a tree T ′ where every set in L is a child
of the smallest set in L that strictly contains it. Note that the leaves of T ′ are in bijection with the
terminals and the root vR that represents R. Consider the directed graph G obtained by adding
an auxiliary vertex s to T ′ connected to vR and orienting the tree away from s. If we put s on the
upper semiaxis, we draw G with all arcs pointing downwards, and we assign capacities to each arc
equal to the capacity of the laminar set associated to the arc’s head we obtain a semiplanar representation of M[R, L, c]. Furthermore, the terminals in R appear in the x-axis in the left-to-right
order induced by the drawing of the tree.
Semiplanar drawings and neighbours. In what follows we fix a semiplanar drawing G of a semiplanar
gammoid M[N ]. We identify R with the set [n] by labeling the terminals from left to right as they
appear in the x-axis. For convenience in the rest of the presentation, we add to G two auxiliary
nodes on the x-axis, 0 and n + 1, where 0 is located to the left of 1, and n + 1 is located to the right
of n, together with the arcs s0 and s(n + 1). Observe that by our assumptions on the drawing, it
is possible to add those arcs without destroying semiplanarity.
For any set J ⊆ [n] and any y ∈ J ∪ {0, n + 1}, we denote by LeftJ (y) the closest element
to y in J ∪ {0} that is located strictly to its left (understanding LeftJ (0) = 0). Similarly, we
denote by RightJ (y) the first element in J ∪ {n + 1} located to the right of y (understanding
RightJ (n + 1) = n + 1). For y ∈ [n] \ J, we call LeftJ+y (y) and RightJ+y (y) its left and right neighbors in J (note that they maybe equal to 0 or n+1 and thus, they are not necessarily elements of J).
Ancestors, tree-order and representatives. In the future we will map each terminal outside an
independent set J to its neighbors in J. For the case in which G is a tree (i.e., for laminar
matroids) we want to consistently assign each element to just one of them. We do this as follows.
For every pair of nodes x, y in G, let xGy be the unique undirected x-y path in G. We say that x is

19

an ancestor of y (and y is a descendant of x) if sGy contains sGx; in that case we denote x ⊒ y (and
y ⊑ x). Note that (V, ⊑) is a partial order, and in fact, it is a join-semilattice where x ∨ y is the
lowest common ancestor of x and y. Note that by our drawing choice, for any i ∈ [j, j ′ ] ⊆ [0, n + 1]
we have i ⊑ j ∨ j ′ . In particular, if [j, j ′ ] ⊆ [k, k ′ ] ⊆ [0, n + 1] then j ∨ j ′ ⊑ k ∨ k′ .
For every nonempty set J ⊆ [n], and for every terminal y ∈ [n], we define its representantive
πJ (y) in J such that


if y ∈ J,
y
πJ (y) = LeftJ+y (y)
if y ∈ [n] \ J and y ∨ LeftJ+y (y) ⊏ y ∨ RightJ+y (y),


RightJ+y (y) if y ∈ [n] \ J and y ∨ LeftJ+y (y) ⊒ y ∨ RightJ+y (y).

This element is well defined since for all y ∈ [n] \ J, both y ∨ LeftJ+y (y) and y ∨ RightJ+y (y)
belong to sGy and so one is an ancestor of the other. Observe that πJ (y) is never equal to 0 (because
then s = 0 ∨ y ⊏ RightJ+y (y) ∨ y which is a contradiction as s is the root), nor n + 1 (because then
s = (n + 1) ∨ y ⊑ LeftJ+y (y) ∨ y ⊑ vR ⊏ s). In particular, πJ (y) ∈ {LeftJ+y (y), y, RightJ+y (y)} ∩ J.
A graphical way to understand the definition of the representative of an element y outside J is the
following: let j and j ′ be the left and right neighbors of y in J respectively and call sGj and sGj ′
the left and right paths respectively. The representative of y is its left neighbor (respectively, its
right neighbor) if and only if by starting from y and walking up on G against its orientation, the
first path hit is the left path (respectively the right path). In case of a tie, the representative is the
right neighbor (see Figure 1).
We claim also that for every j ∈ J, the set of elements to its right having j as representative
is an interval of the form [j, k] with k < RightJ (j). Indeed, this is true if RightJ (j) = n + 1.
Suppose now that j ′ := RightJ (j) ≤ n, and that the claim does not hold. Then, there must be
two consecutive terminals i, i + 1 ∈ (j, j ′ ) with πJ (i + 1) = j and πJ (i) = j ′ . But then, we get the
following contradiction:
(i + 1) ∨ j ′ ⊑ i ∨ j ′ ⊑ i ∨ j ⊑ (i + 1) ∨ j ⊏ (i + 1) ∨ j ′
where the first inequality holds since [i + 1, j ′ ] ⊆ [i, j ′ ], the second, by the definition of πJ (i),
the third since [j, i] ⊆ [j, i + 1] and the fourth by definition of πJ (i + 1). Since every element
in (j, j ′ ) either has j or j ′ as representative, we conclude, in fact, that the entire set πJ−1 (j) of
elements with j as representative is an interval of terminals enclosing j but strictly contained in
[LeftJ (j), RightJ (j)]. In other words (πJ (j))j∈J is a partition of [n] into |J| intervals.
The algorithms. In what follows we describe our algorithms for semiplanar gammoids and laminar
matroids. Apart from some special case occurring when the sample is empty, our algorithms are
extremely simple. Each one computes the optimal solution OPT(Rs ) of the sample and leave their
elements unmarked. When a terminal ri that is part of the current optimum arrives, it checks if the
(closest neighbors / representative) of ri in OPT(Rs ) (are / is) unmarked. If so, it marks (them /
it) and selects ri as part of the solution.

20

5
4
3

3
2

0

1

2

2

2

3

4

5

6

7

8

9

2

10

11

12

13

2

14

15

16

17

18

Figure 1: Semiplanar drawing of a laminar matroid with ground set [17]. Nonunit arc capacities are shown.
Below we show the partition (πJ (j))j∈J induced by the independent set J = {3, 5, 10, 13, 15}.

Algorithm 6 for semiplanar gammoids.

Algorithm 7 for laminar matroids.

Input: An semiplanar gammoid with a fixed semiplanar
drawing
1: ALG ← ∅, s ← Bin(n, p),
2: if s = 0 then
3: ALG ← {r1 }
4: else B ← ∅.
5: for i = s + 1 to n do
6:
if ri ∈ OPT(Ri ), LeftOPT(Rs )+ri (ri ) 6∈ B and
RightOPT(Rs )+ri (ri ) 6∈ B then
7:
ALG ← ALG + ri , and
B ← B ∪ {LeftOPT(Rs )+ri (ri ), RightOPT(Rs )+ri (ri )}

Input: A laminar matroid with a fixed
semiplanar drawing
1: ALG ← ∅, s ← Bin(n, p),
2: if s = 0 then
3:
ALG ← {r1 }
4: else B ← ∅.
5:
for i = s + 1 to n do
6:
if ri ∈ OPT(Ri ) and
πOPT(Rs ) (ri ) 6∈ B then
7:
ALG ← ALG + ri , and
B ← B ∪ {πOPT(Rs ) (ri )}.

8: Return ALG.

8: Return ALG.

Theorem 15. Algorithm 6 has forbidden sets of size 4. By setting p = p(4) =
α(4) = 44/3 ≈ 6.3496 probability-competitive algorithm for semiplanar ACGs.

p
3

1/4 we get an

The previous result applied
to laminar matroids already beat the best guarantees known for
√
that class (9.6 [39] and 3 3e [25, 26]). But we can do better for laminar matroids since for those,
there is a unique path from the source to each terminal.
p
Theorem
√ 16. Algorithm 7 has forbidden sets of size 3. By setting p = p(3) = 1/3 we get an
α(3) = 3 3 probability-competitive algorithm for laminar matroids.
√
We observe that this algorithm is very similar to the 3 3e competitive algorithm of Jaillet et
al. [25, 26]. Note that the partition of the terminals given by πOPT(Rs ) induces a unitary partition
matroid P ′ . After the sample, Algorithm 7 simply selects on each part, the first arriving element
that is part of the current optimum. It can be shown that the partition matroid P ′ we define is
the same as the one defined in [26, Section 3.2]. The main algorithmic difference is that in [26], the
authors use the algorithm for the classic secretary problem to select one terminal on each part that
has constant probability of being the largest element. Instead, we select the first arriving element
21

on each part that is part of the optimum at the time of arrival. This small change makes the
competitive ratio of our algorithm e times smaller than theirs, but the analysis is more involved.
To prove Theorems 15 and 16 we need to develop some extra tools.
The unit capacity semiplanar gammoid associated to an independent set and its standard arc-covering. For every nonempty independent set J ⊆ [n] in the semiplanar gammoid
M[N ] we chose an arbitrary but fixed s-J flow fJ satisfying the arc capacity constraints. Define
the unit capacity network N 1 (J) = (G1 (J), s, R, 1), where G1 (J) is obtained from G by splitting
each arc uv with fJ (uv) ≥ 2 into fJ (uv) parallel arcs (we keep all arcs uv with fJ (uv) ∈ {0, 1}, we
also keep the arcs s0 and s(n + 1)). We do this in such a way that G1 (J) is still semiplanar. The
matroid M[N 1 (J)] is the unit capacity semiplanar gammoid associated to J.
Observe that every path in G1 (J) corresponds canonically to an unsplitted path in G going
through the same nodes. Furthermore, every arc-disjoint collection P of s-R paths in G1 (J) can
be regarded, by unsplitting parallel arcs, as an s-R flow on G satisfying the capacity constraints.
Therefore, we have the following important lemma.
Lemma 17. Any independent set in M[N 1 (J)] is also independent in the original matroid M[N ].
We say that two paths P and Q in the drawing of a graph cross if P enters Q on the left,
shares zero or more arcs with Q and then exits Q on the right, or viceversa. A collection of paths is
mutually noncrossing if no pair of them cross.7 The s-J flow fJ in the network N can be mapped to
an s-J flow fJ1 in N 1 (J) in a natural way. By applying flow-decomposition on fJ1 we get a collection
{P k }k∈J of arc-disjoint paths. Define also P 0 and P n+1 as the paths consisting of a single arc s0
and s(n + 1) respectively. By a standard planar uncrossing argument, we can assume that all paths
in {P k }k∈J∪{0,n+1} are mutually noncrossing (but they can still share internal nodes, in fact all
paths P k with k ∈ J contain s and vR , see Figure 2). For j ∈ J + 0, call j ′ = RightJ+0 (j) and
define the collection of arcs Aj ⊆ E(G1 (J)) as those that are drawn in the closed planar region
′
Rj bounded by P j , P j and the x-axis. Since paths {P k }k∈J∪{0,n+1} form a topological star whose
tips are in the x-axis we conclude that {Rk }k∈J+0 is a division of the region bounded by P 0 , P n+1
and the x-axis, and thus {Ak }k∈J+0 is a covering of all arcs in G1 (J). In fact, if 1 ≤ j ′ 6= n + 1,
′
′
then every arc of P j belongs to pieces Aj and Aj , while each arc in G1 (J) \ {P k }k∈J belongs to
a single piece of the covering. Furthermore, the only terminals contained in region Rj are those in
[j, j ′ ].
Lemma 18. Let y ∈ [n] \ J, and j = LeftJ+y (y), j ′ = RightJ+y y be its neighbors in J. Then there
is a directed s-y path DJ (y) in G1 (J) whose arc set is completely contained in Aj . Furthermore,
DJ (y) can be chosen so that it arcs-intersects at most one path P̄ in (P k )k∈J . In the semiplanar
′
case, P̄ must be one of P j and P j , and in the laminar case, P̄ = P πJ (ℓ) .
Proof. Note that y ∈ [j, j ′ ] is in the planar region Rj . Since y is reachable from s in G, there is a
′
path Q from s to y in G1 (J). Let v be the last vertex in Q contained in the vertices of P j and P j
′
(v maybe in one or both paths), say v is in P̄ ∈ {P j , P j }. By concatenating the initial piece of P̄
7

An alternative way to understand this definition is to imagine that in the drawing nodes and arcs have positive
area (they are circles and thick lines). A drawing of a path is any continuous non-self-intersecting curve drawn inside
the union of all circles and thick lines associated to the nodes and arcs of P visiting them in the correct order. A
collection of paths are mutually noncrossing if we can find drawings such that no pair of them intersects. Note that
two noncrossing paths can still share arcs and nodes.

22

3

2

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

1

2

3

4

5

6

7

8

9

10

11

12

13

Figure 2: On the left, a flow fJ associated to the independent set J = {1, 4, 6, 11} on a semiplanar gammoid

M[N ] with ground set R = [13] (0 and 14 are auxiliary nodes). On the right, M[N 1 (J)] and the partition
of the drawing into regions R0 , R1 , R4 , R6 and R11 induced by the paths {P j }j∈J∪{0,14} . The regions R0 ,
R4 and R11 are shaded.

from s to v and the final piece of Q from v to y we get a path DJ (y) that is completely contained
in Aj and that intersects the arcs of at most one path in {Pj , Pj ′ }.
′
Consider the same situation in the laminar case. All arcs in P j , P j and Q are splitted versions
of arcs in sGj, sGj ′ and sGy respectively. The vertex v defined above satisfies v = y ∨ j ∨ j ′ . If
′
y ∨ j ⊏ y ∨ j ′ then v = y ∨ j, πJ (y) = j and we can construct DJ (y) avoiding all arcs in P j by
selecting P̄ = P j in the previous argument. Analogously, if y ∨ j ′ ⊑ y ∨ j then v = y ∨ j ′ , πJ (y) = j ′ ,
′
and we can choose DJ (ℓ) to avoid P j by setting P̄ = P j .
Lemma 19. Let J ⊆ [n] be a nonempty independent set in M[N ] and I ⊆ [n] \ J. Consider the
following properties.
(P1) For every x, y ∈ I with x 6= y, {LeftJ+x (x), RightJ+x (x)} ∩ {LeftJ+y (y), RightJ+y (y)} = ∅.
(P2) M[N ] is laminar and for every x, y ∈ I, πJ (x) 6= πJ (y).
If either (P1) or (P2) holds then I is independent in M[N 1 (J)]
Proof. Suppose that (P 1) is satisfied. Then for every pair of distinct x, y ∈ I, the paths DJ (x)
and DJ (y) constructed in Lemma 18 must lie on non-consecutive (and hence disjoint) regions in
{Rk }k∈J+0 . Therefore the paths {DJ (z)}z∈I are mutually arc-disjoint from which we conclude that
I is an independent set in M[N 1 (J)].
Suppose now that (P 2) is satisfied. Let x < y be distinct terminals in I. We claim that
the paths DJ (x) and DJ (y) are arc disjoint. If x and y belong to different regions then the only
possibility for them to share an arc is that x is in Rj , y ∈ Rj ′ with j ′ = RightJ (j), and both share
′
arcs in P j . But then, by Lemma 18, πJ (x) = πJ (y) = j ′ which is a contradiction.
If x and y are in the same region Rj , then x, y ∈ [j, j ′ ] with j = LeftJ+x (x) = LeftJ+y (y) and
′
j = RightJ+x (x) = RightJ+y (y) ∈ J + (n + 1). Since the function πJ partitions [n] into intervals
and x < y, we must have πJ (x) = j, πJ (y) = j ′ . Suppose now that DJ (x) and DJ (y) had an arc a
in common and let w be its head. Since DJ (x) and DJ (y) are split versions of sGx and sGy we get
that w ⊒ x ∨ y. Since w and x ∨ j are both in sGx, one is an ancestor of the other. Note that w
cannot be an ancestor of x ∨ j since above the latter DJ (x) coincides with P j which is arc-disjoint
from DJ (y) by Lemma 18 (and a is a common arc). It follows that x ∨ j ⊐ w ⊒ x ∨ y ⊒ y, and thus,
23

14

x ∨ j ⊒ y ∨ j. But since πJ (y) = j ′ we have y ∨ j ⊒ y ∨ j ′ and we conclude that x ∨ j ⊒ y ∨ j ′ ⊒ j ′ .
From the last expression we get x ∨ j ⊒ x ∨ j ′ which contradicts the fact that πJ (x) = j.
We have thus shown that all paths (DJ (z))z∈I are arc-disjoint, thence I is independent in
M[N 1 (J)]
Now we are ready to define the forbidden sets of sizes at most 4 and 3 respectively for Algorithms
6 and 7. For (X, r ∗ ) with r ∗ ∈ [n], X ⊆ [n] \ {r ∗ } define the sets
F4 (X, r ∗ ) = {LeftX (LeftX+r∗ (r ∗ )), LeftX+r∗ (r ∗ ), RightX+r∗ (r ∗ ), RightX (RightX+r∗ (r ∗ ))}
I4 (X, r ∗ ) = [LeftX (LeftX+r∗ (r ∗ )), RightX (RightX+r∗ (r ∗ ))].

The set F4 (X, r ∗ ) contains the 2 closest terminals to the left of r ∗ in X and the 2 closest terminals
to its right. I4 (X, r ∗ ) is the enclosing interval containing F4 (X, r ∗ ). Similarly, for the case of
laminar matroids, define
F3 (X, r ∗ ) = {LeftX (πX (r ∗ )), πX (r ∗ ), RightX (πX (r ∗ ))}
I3 (X, r ∗ ) = [{LeftX (πX (r ∗ )), RightX (πX (r ∗ ))}].

where F3 (X, r ∗ ) consists of the representative of r ∗ in X and its two neighbors, and I3 (X, r ∗ ) is its
enclosing interval. We need one last technical lemma to analize the algorithms performance.
Lemma 20. Let X and r ∗ as above, and let x ∈ X.
(a) If x ∈ F4 (X, r ∗ ) then I4 (X, r ∗ ) ⊆ I4 (X − x, r ∗ ).
(b) If x 6∈ F4 (X, r ∗ ) then F4 (X, r ∗ ) = F4 (X − x, r ∗ ) and I4 (X, r ∗ ) = I4 (X − x, r ∗ ).
If the matroid is laminar, the following properties also hold
(c) If x ∈ F3 (X, r ∗ ) then I3 (X, r ∗ ) ⊆ I3 (X − x, r ∗ ).
(d) If x 6∈ F3 (X, r ∗ ) then F3 (X, r ∗ ) = F3 (X − x, r ∗ ) and I3 (X, r ∗ ) = I3 (X − x, r ∗ ).
Proof of Lemma 20.
Part (a): Let F4 (X, r ∗ ) = {a, b, c, d} from left to right (note that near the borders we could have
a = b or c = d), in particular a ≤ b ≤ r ∗ ≤ c ≤ d. Denote by a− = LeftX (a) and d+ = RightX (d).
(i) If x ∈ {a, b} then F4 (X − x, r ∗ ) = (F4 (X, r ∗ ) − x) + a− and so I4 (X, r ∗ ) = [a, d] ⊆ [a− , d] =
I4 (X − x, r ∗ ).
(ii) If x ∈ {c, d} then F4 (X − x, r ∗ ) = (F4 (X, r ∗ ) − x) + d+ and so I4 (X, r ∗ ) = [a, d] ⊆ [a, d+ ] =
I4 (X − x, r ∗ ).
Part (b): Direct.
For parts (c) and (d) let F3 (X, r ∗ ) = {a, b, c} from left to right (in particular b = πX (r ∗ ),
note that we could be in the cases a = b = 0 or b = c = n + 1). Denote by a− = LeftX (a) and
c+ = RightX (c).
Part (c): We have many possibilities to analyze.
(i) If x = b, then the closest neighbors of r ∗ in X − x are a and c. In particular πX−x (r ∗ ) is
either a or c. In both cases, I3 (X, r ∗ ) = [a, c] ⊆ I3 (X − x, r ∗ ).
(ii) If x = a 6= b and r ∗ ∈ [b, c], then b and c are still the closest neighbors of r ∗ in X − x, and
in particular, the representative in X − x is the same as that in X, i.e., πX−x (r ∗ ) = b. Note
that since we removed a, LeftX−x (b) = a− and so, I3 (X, r ∗ ) = [a, c] ⊆ [a− , c] = I3 (X − x, r ∗ )
24

(iii) The case x = c 6= b and r ∗ ∈ [a, b] is analogous to the previous one
(iv) If x = a 6= b, and r ∗ ∈ [a, b], then the closest neighbors of r ∗ in X − x are a− and b.
We have that r ∗ ∨ b ⊑ r ∗ ∨ a ⊑ r ∗ ∨ a− where the first inequality holds since πX (r ∗ ) = b
and the second one since [a, r] ⊆ [a− , r ∗ ]. We conclude that πX−x (r ∗ ) = b. In particular
I3 (X, r ∗ ) = [a, c] ⊆ [a− , c] = I3 (X − x, r ∗ ).
(v) If x = c 6= b and r ∗ ∈ [b, c] then the closest neighbors of r ∗ in X − x are b and c+ . We
have that r ∗ ∨ b ⊏ r ∗ ∨ c ⊑ r ∗ ∨ c+ where the first inequality holds since πX (r ∗ ) = b and
the second holds since [r ∗ , c] ⊆ [r ∗ , c+ ]. We conclude that πX−x (r ∗ ) = b. In particular
I3 (X, r ∗ ) = [a, c] ⊆ [a, c+ ] = I3 (X − x, r ∗ ).
Part (d): Since x 6∈ F3 (X, r ∗ ) the neighbors of r ∗ in X−x are the same as those in X, it follows that
πX−x (r ∗ ) = πX (r ∗ ) = b, LeftX−x (b) = a, RightX−x (b) = c. Therefore F3 (X − x, r ∗ ) = F3 (X, r ∗ )
and I3 (X − x, r ∗ ) = I3 (X, r ∗ ).
Now we are ready to prove the guarantees for Algorithms 6 and 7.
Proofs of Theorems 15 and 16.
For both algorithms, if s = 0 then |ALG| = 1 and so it is independent. In the following assume
that s ≥ 1. Line 6 in the algorithms guarantees that the set ALG satisfies the conditions of Lemma
19, hence ALG is independent in M[N 1 (J)], and by Lemma 17, ALG is independent in the original
matroid. This proves correctness. Since the sampling condition holds by construction, we only
need to check the forbidden property. For the rest of the proof, define F(X, r ∗ ) = Fi (X, r ∗ ),
I(X, r ∗ ) = Ii (X, r ∗ ) where i = 4 on the semiplanar case, and i = 3 for the laminar case. We will
show that the sets F(X, Y, r ∗ ) := F(X, r ∗ ) ∩ [n] are forbidden sets of size at most 4 for Algorithm
6 and of size 3 for Algorithm 7.
Let r ∗ ∈ OPT(Y ) where Y is an arbitrary set of t ≥ s + 1 elements, and suppose that Rt = Y
and rt = r ∗ . Assume now that the condition
for every i ∈ {s + 1, . . . , t − 1}, ri 6∈ F(OPT(Ri ), rt ),

(⋆)

holds. We have to show that rt = r ∗ is chosen by the algorithm.
Claim. The intervals I(OPT(Ri ), r ∗ ) are non-decreasing in i, namely, for all i ≤ t − 2,
I(OPT(Ri ), r ∗ ) ⊆ I(OPT(Ri+1 ), r ∗ ).
Indeed, let i ≤ t − 2. If OPT(Ri ) = OPT(Ri+1 ) then the claim is trivial, so assume otherwise. In
particular, we have ri+1 ∈ OPT(Ri+1 ) \ OPT(Ri ). To simplify notation, let A = OPT(Ri+1 ) and
A′ = A − ri+1 . By condition (⋆), ri+1 6∈ F(A, r ∗ ), and then by Lemma 20 using X = A,
F(A, r ∗ ) = F(A′ , r ∗ ) and I(A, r ∗ ) = I(A′ , r ∗ ).

(6)

By the matroid exchange axiom we have two cases: either OPT(Ri ) = A′ or OPT(Ri ) = A′ + r̃
for some r̃ 6= ri+1 . In the first case we have by (6) that I(OPT(Ri ), r ∗ ) = I(A′ , r ∗ ) = I(A, r ∗ ) =
I(OPT(Ri+1 ), r ∗ ), which ends the proof, and so we focus on the the second case. If r̃ ∈ F(A′ + r̃, r),
then by (6) and Lemma 20 applied to X = A′ + r̃, we have I(OPT(Ri ), r ∗ ) = I(A′ + r̃, r ∗ ) ⊆
I(A′ , r ∗ ) = I(A, r ∗ ) = I(OPT(Ri+1 ), r ∗ ). On the other hand, if r̃ 6∈ F(A′ + r̃, r), then, again
by Lemma 20 and and (6) we have I(OPT(Ri ), r ∗ ) = I(A′ + r̃, r ∗ ) = I(A′ , r ∗ ) = I(A, r ∗ ) =
I(OPT(Ri+1 ), r ∗ ). This concludes the proof of the claim.
25

We show how to finish the proof of the lemma using the claim. Suppose that ri is selected by the
algorithm for some i ∈ {s+1, . . . , t−1}. By (⋆) and the claim we deduce that ri 6∈ I(OPT(Ri ), r ∗ ) ⊇
I(OPT(Rs ), r ∗ ). In particular ri is far away from r ∗ :
(a) In the semiplanar case, there are at least 2 terminals of OPT(Rs ) between r ∗ and ri . In particular, {LeftOPT(Rs )+ri (ri ), RightOPT(Rs )+ri (ri )} and {LeftOPT(Rs )+r∗ (r ∗ ), RightOPT(Rs )+r∗ (r ∗ )}
do not intersect and so, at iteration i, neither LeftOPT(Rs )+r∗ (r ∗ ) nor RightOPT(Rs )+r∗ (r ∗ ) are
added into B.
(b) In the laminar case, there is at least one terminal of OPT(Rs ) between πOPT(Rs ) (r ∗ ) and ri .
In particular, πOPT(Rs ) (ri ) 6= πOPT(Rs ) (r ∗ ), and so, at iteration i, πOPT(Rs ) (r ∗ ) is not added
into B.
Since the statements above are satisfied for every i ≤ t − 1, we conclude that at time t, rt = r ∗
satisfies the conditions in line 6 of the algorithms, and so it is selected. This concludes the proof
that Algorithms 6 and 7 have forbidden sets of sizes 4 and 3 respectively.

3.7

Uniform matroids

We devise a variant of Kleinberg’s algorithm [31] for uniform matroids whose probability competitiveness tends to 1 as the rank ρ goes to infinity. Kleinberg’s algorithm is better described when
both the rank ρ = 2k and the number of elements n = 2N are powers of 2. It was originally
presented in a recursive manner, but it is illustrative to describe it without using recursion:
Kleinberg’s algorithm. For every i ∈ N, let Ii be the interval of the first n/2i elements. Then the
intervals Jk := Ik , Jk−1 := Ik−1 \ Ik , . . . , J1 := I1 \ I2 and J0 = I0 \ I1 partition the ground set R.
The algorithm treats each interval in {J0 , J1 , . . . , Jk } separately. For 0 ≤ i ≤ k − 1, it selects at
most bi = ρ/2i+1 elements from Ji and at most one element from Jk , so that in total at most ρ
elements are selected. The way the algorithm selects an element or not is determined by a threshold
for each interval. Namely, it selects the first arriving element from Jk and for i ∈ {0, 1, . . . , k − 1},
the algorithm uses as threshold in the interval Ji the (ρ/2i )-th highest element seen strictly before
the interval, i.e., the (ρ/2i )-th element of Ii+1 . It selects every element better than this threshold
until the budget bi of the interval is depleted, ignoring all the elements arriving later in this interval.
The probability-ratio of Kleinberg’s algorithm is at least 4/3. Kleinberg
p [31] shows that the previous algorithm is guaranteed to obtain an expected
p fraction 1 − O(
p 1/ρ) of the optimum weight,
which in our notation means to be 1/(1 − O( 1/ρ)) = 1 + O( 1/ρ) utility-competitive. This
guarantee also holds for the ordinal notion since the algorithm does not need weights. However, as
we show next, its probability competitiveness is bounded away from 1. Since J0 and I1 have the
same cardinality, with probability tending to 1/4 as ρ goes to infinity, we simultaneously have that
|I1 ∩ Rρ−1 | < |J0 ∩ Rρ−1 | and r ρ ∈ J0 . Given that, the threshold for J0 , which is the ρ/2-th element
of I1 , will be attained by an element of Rρ−1 which is strictly better than r ρ . Thus, r ρ will not be selected. Therefore, the algorithm selects r ρ (which is in OPT) with probability at most 1−1/4 = 3/4.
An asymptotically 1 probability-competitive algorithm. The next algorithm is a simple modification
of Kleinberg’s, which we write in a continuous setting. Every element is associated with a uniform
random variable with support [0, 1). It is useful for this part to imagine [0, 1) as a time interval,
and identify the realization of the uniform random variable as the arrival time of the element.
For each j ∈ N, let Ij be the interval [0, 2−j ) and Jj = [2−j−1 , 2−j ) to be its second half. The
26

sequence {Jj }j≥0 partitions the interval [0, 1). For convenience, let Kj = [2−j−1 , 2−j−1 (2 − 4εj )) be
the left (1−4εj ) fraction of the interval Jj , for some parameter εj , depending on ρ, to be chosen later.
Algorithm 8 for uniform matroids.
Input: A uniform matroid U (n, ρ) with ground set R and rank ρ.
1: Get a sample of size n, independently and uniformly at random from [0, 1). Sort it from smallest
to largest as t1 < t2 < · · · < tn . Thus ti is interpreted as the arrival time of ri .
2: ALG ← ∅
3: for i = 1 to n do
4:
Compute the index j such that ti ∈ Jj = [2−j−1 , 2−j ).
5:
Compute the threshold fj equal to the ⌈( 21 )j+1 (1 + εj )ρ⌉-th highest element in Ri with
arrival time in Ij+1 = [0, 2−j−1 ).
6:
if less than ( 12 )j+1 ρ elements with arrival time in Jj have been selected and ri ≻ fj then
7:
ALG ← ALG + ri
8: Return ALG.
..
.
I3

J2

I2

J1

I1
I0

J0
0

· · · 0.25

0.5

1

Figure 3: Definition of the sets Ij and Jj
p
Theorem 21. Algorithm 8 is 1 + O( log ρ/ρ) probability-competitive.
√
By going from utility to probability we incur in a factor of log ρ on the error probability. It
√
remains open whether we can achieve Kleinberg’s optimal utility-competitiveness of 1 + O(1/ ρ)
for the stronger probability notion.
Proof of Theorem
the algorithm selects at most (1/2)j+1 ρ elements from interval Jj , in
P∞21. Since
j+1
total at most j=0 (1/2) ρ = ρ elements are included into ALG. Therefore, the algorithm is
correct. Since the matroid is uniform of rank ρ, the optimal base is OPT = {r 1 , r 2 , . . . , r ρ }.
Let r ∗ = r k ∈ OPT, for some k ∈ {1, . . . ,p
ρ}. In what follows, let j be an integer such that
1
∗
0 ≤ j ≤ ⌊ 2 log(ρ/96)⌋ := j and let εj = 12 · 2j ln ρ/ρ. We first find a lower bound on the
probability that r ∗ is selected, given that its arrival time is in Jj .
(j)
(j)
For each r i ∈ R − r ∗ , let Xi and Yi be the indicator variables that the arrival time of r i is
in Ij+1 and Kj respectively. Let σ(fj ) be the global ranking of the computed threshold fj , that is,
r σ(fj ) = fj . Consider the following three events,
X

(j)

Xi

i∈[ρ+1]\{k}

<

(1 + εj )
ρ,
2j+1

X

(j)

Xi

 1+εj  

i∈

1−εj

ρ +1 \{k}

27

≥

1 + εj
ρ,
2j+1

X

 1+εj  

i∈

1−εj

(j)

Yi

ρ +1 \{k}

<

1
2j+1

ρ,

that we call U1 , U2 and U3 respectively. Consider a fourth event, U4 , that is tk ∈ Kj where tk
is the arrival time of r k . We claim that provided tk ∈ Jj , the intersection of these four events
guarantees that r ∗ is selected by the algorithm. Conditional on the event that tk ∈ Jj , event
U1 ∩ U2 implies that ρ + 1 < σ(fj ) ≤ ⌈(1 + εj )ρ/(1 − εj )⌉ + 1 and r ∗ ≻ fj . Event U2 ∩ U3
implies that the number of elements strictly higher than the threshold fj and arriving on interval
Kj is strictly less than ( 21 )j+1 ρ. In particular, this implies that the algorithm has not selected
enough elements in the interval Jj . Therefore, conditional on the event that tk ∈ Jj , the event
U1 ∩ U2 ∩ U3 ∩ U4 implies that r ∗ ∈ ALG. Calling Ui to the negation of event Ui , by union
bound and noting that events
from 1 to 3 are independent of the arrival time of r ∗ = r k , we have
P
4
Pr(r k 6∈ ALG | tk ∈ Jj ) ≤ i=1 Pr(Ui | tk ∈ Jj ) = Pr(U1 ) + Pr(U2 ) + Pr(U3 ) + 4εj .
(j)
The random variables {Xi }i∈[n]\{k} are independently and identically Bernoulli distributed of
(j)

parameter equal to the length of Ij+1 , that is 2−j−1 . Similarly, the random variables {Yi }i∈[n]\{k}
are independently and identically Bernoulli distributed of parameter equal to the length of Kj that
is (1 − 4εj )2−j−1 . In the following we upper bound the probabilities in the sum above by using the
Chernoff bound [40, p. 64-66, Theorems 4.4 and 4.5].

 12 · 2j ln ρ


 1
 ε2
j
Pr(U1 ) ≤ exp − 2−j−1 ρ = exp −
2−j−1 ρ = exp −2 ln ρ ≤ .
3
3ρ
ρ
(j)

(j)

Let µX and µY be the expected sums of the random
variables
Xi , and respectively Yi , for
l
m 
 1+εj 

1+ε
1+εj
ρ
1 j+1
. The choice of j
i ∈ 1−εj ρ + 1 \ {k}. For µX we have µX = 1−εj ρ 2
≥ 1−εjj · 2j+1
guarantees that 1/ρ < ǫj < 1/8, and therefore




1 + εj
1 − 4εj
1 + εj
(1 − 4εj )(1 + 2εj ) ρ
1 − 4εj
1
ρ
µY =
ρ
≤
+ εj ρ · j+1 ≤
≤
·
.
1 − εj
2j+1
1 − εj
2
1 − εj
2j+1
1 + εj 2j+1
In the last inequality we used that εj < 1/8. By Chernoff bound on events U2 and U3 , we obtain
 ε2

 12 · 2j ln ρ 1 + ε
X (j)
ρ  1
j
j
Xi < µX (1 − εj )) ≤ exp − µX ≤ exp −
·
· j+1 ≤ ,
Pr(U2 ) ≤ Pr(
2
2ρ
1 − εj 2
ρ
i

 ε2 
 12 · 2j ln ρ 1 + ε (1 − 4ε )ρ  1
X (j)
j
j
j
Yi ≥ µY (1 + εj )) ≤ exp − µY ≤ exp −
Pr(U3 ) ≤ Pr(
·
·
≤ .
3
3ρ
1 − εj
2j+1
ρ
i

Putting all together, it follows that
∗

k

Pr(r 6∈ ALG) =
≤

X

Pr(r 6∈ ALG|t ∈ Jj )

X

X

j>j ∗

j>j ∗

k

1
2j+1

+

1

k

j≥0

3
+ 4εj
ρ

2j+1



+

1
2j+1

j
X
j=0

=

Pr(r k 6∈ ALG|tk ∈ Jj )
1

2j ∗ +1

+



1
2j+1

s

3
12 ln ρ X j/2 1
2
+4
,
ρ
ρ
2j+1
j≥0

q
q

q

p
log ρ
log ρ
1
1
which is O
+
+
=
O
. Therefore, the algorithm is 1/(1 − O( log ρ/ρ)) =
ρ
ρ
ρ
ρ
p
(1 + O( log ρ/ρ)) probability-competitive.
28

4
4.1

Algorithms for the ordinal MSP on general matroids
O(1) intersection-competitiveness: Proof of Theorem 2

Our algorithm for the intersection notion works as follows. We first sample s elements. After that,
we select an element as long as it is part of the optimum of the subset of elements seen so far, and
it preserves the independence of the current solution. Recall that we denote by Ri = {r1 , r2 , . . . , ri }
the first i elements seen by the algorithm.
Algorithm 9 Improving Greedy
Input: Matroid M(R, I) in random order r1 , r2 , . . . , rn , and a fixed integer s ∈ {1, . . . n}.
1: ALG ← ∅
2: for i = s + 1 to n do
3:
if ri ∈ OPT(Ri ) and ALG + ri ∈ I then
4:
ALG ← ALG + ri .
5: Return ALG.
The idea of only considering elements that belong to the current optimum is not new. Ma et
al. [39] consider an algorithm that after sampling a fraction, selects an element as long as it belongs
to the current offline optimum, and they prove this to be 9.6 utility-competitive (and the analysis
holds for probability as well) for laminar matroids. The same algorithm was suggested by Babaioff
et al. [5], and they showed how this algorithm fails to be even constant utility-competitive. In
contrast, we show this algorithm to be O(1) intersection-competitive.
Lemma 22. Let B = {ri : ri ∈ OPT(Ri ), i ∈ {s + 1, . . . , n}}. Then E[|B|] = (Hn − Hs )ρ, where
Hj denotes the j-th harmonic number.

Proof. For every i ∈ [n] if we condition the set Ri to be some fixed set F ∈ Ri , we have
Pr(ri ∈ OPT(Ri )|Ri = F ) = Pr(ri ∈ OPT(F )) ≤

ρ
.
i

Therefore, by linearity of expectation we conclude that
E[|B|] =

n
X

i=s+1

n
X
ρ
Pr(ri ∈ OPT(Ri )) ≤
= (Hn − Hs )ρ.
i
i=s+1

Proof of Theorem 2. We study the competitiveness of the algorithm when the sample size is s, and
then we optimize over this value to conclude the theorem. For any random ordering, |ALG| =
ρ(R \ Rs ) ≥ ρ(OPT \ Rs ) = |OPT \ Rs |. Then, E[|ALG ∩ OPT|] equals
E[|ALG|] + E[|OPT \ Rs |] − E[|ALG ∪ (OPT \ Rs )|] ≥ 2E[|OPT \ Rs |] − E[|ALG ∪ (OPT \ Rs )|].
Furthermore, ALG ∪ (OPT \ Rs ) ⊆ B, where B is the set defined in Lemma 22. Since the elements
arrive in uniform random order, for r ∈ OPT we have that Pr(r ∈
/ Rs ) = (n − s)/n = 1 − s/n.
Therefore, the right hand side of the previous inequality is at least




Z n
1
2s
2s
−
dx ρ = 2 −
+ ln(s/n) ρ.
2E[|OPT \ Rs |] − E[|B|] ≥ 2 −
n
n
s x
29

This quantity is maximized in s = n/2. So, by assuming n even (which can be done by adding an
extra dummy element if n is odd), and setting the algorithm for s = n/2, we obtain
E[|ALG ∩ OPT|] ≥ ρ(1 − ln(2)) = |OPT|/ ln(e/2).

4.2

Ordinal/Probability-competitiveness: Proof of Theorem 3

We introduce a variant of the MSP that helps us to leverage existing algorithms for the utility
version of the MSP, in order to get competitive algorithms for the ordinal and probability variants.
We need a concept similar to the aided sample-based MSP introduced by Feldman et al .[19].
In the Layered-MSP the input is a tuple (M, F, C, ≻) where M = (R, I, ≻) is a totally ordered
matroid, C = {c1 , c2 , . . . , ck } is a finite set with C ∩ R = ∅, ≻ is a total order over R ∪ C with
c1 ≻ c2 ≻ · · · ≻ ck , and F is a random subset of R in which every element is present with probability
1/2. The set C defines a partition of R in the following way. We call C0 = {r ∈ R : r ≻ c1 } the
highest layer and Ck = {r ∈ R : ck ≻ r} the lowest layer. For j ∈ {1, . . . , k − 1}, the j-th layer is
the set Cj = {r ∈ R : cj ≻ r ≻ cj+1 }. By construction, the layers {C0 , C1 , . . . , Ck } induced by C
form a partition of R. In the following we call a tuple (M, F, C, ≻) as a layered matroid.
An algorithm for the Layered-MSP first sees F but is unable to select any of its elements. The
rest of the elements of M arrive in uniform random order. At time step t, the algorithm can get
the full value order in Rt by using only ordinal information, it can use an independence oracle to
test any subset of Rt and it can also check membership of any element to each layer induced by C.
Definition 23. We say that an algorithm for the Layered-MSP is α-competitive if it returns an
independent set ALG ∈ I, and for each j ∈ {0, 1, . . . , |C|}, E|ALG ∩ Cj | ≥ α1 |OPT ∩ Cj |, where the
expectation is taken both over the distribution of F and the internal algorithm randomness.
Theorem 24 (Feldman et al., [19, Corollary 4.1]). There exists an 8⌈log(|C| + 1) + 1⌉-competitive
algorithm for the Layered-MSP.
For the sake of completeness we include the mentioned algorithm for Layered-MSP of Feldman et
al. We remark that the algorithm was introduced in the context of the utility version. Nevertheless,
the result above follows in the absence of weights.
Algorithm 10 (Feldman et al. [19]) for Layered-MSP
Input: A layered matroid (M, F, C, ≻)
1: Let τ be a uniformly at random number from {0, 1, . . . , ⌈log(|C| + 1)⌉}.
2: Let ∆ be a uniformly at random number from {0, 1, . . . , 2τ − 1}.
Smin{|C|,2τ i−∆}
3: Let B = {B1 , B2 , . . . , B⌈(∆+|C|)/2τ ⌉ } where Bi = j=max{0,2τ (i−1)−∆+1} Cj .
4: With probability 1/2, set H = odd(|C|) or even(|C|) otherwise.
5: For each i ∈ H let Ti ← ∅.
6: for each element in r ∈ R \ F do
7:
Let i be such that r ∈ Bi .
8:
if i ∈ H and r ∈ Ni and Ti + r ∈ Ii then
9:
Ti ← Ti + r.
10: Return ALG = ∪i∈H Ti .

30

About the algorithm of Feldman et al. We denote by odd(k) and even(k) the odd and even numbers,
respectively, in the set {0, 1, . . . , k}. The set Ii is the independent sets family of a matroid Mi =
(Ni , Ii ) defined as follows. Let B≥i = ∪j∈{i,...,⌈(∆+|C|)/2τ ⌉} Bj . The matroid M1 is obtained from
M by contracting 8 F ∩ B≥2 and then restricting9 to B1 . For i > 1, Mi is obtained from M by
contracting F ∩ B≥i+1 and then restricting it to Bi ∩ span(F ∩ B≥i−1 ).
4.2.1

Reduction from Layered-MSP to ordinal and probability variants of the MSP

The main result of this section corresponds to the lemma below. Theorem 3 follows directly using
this lemma, and the rest of this section is devoted to prove the lemma.
Lemma 25. Suppose there exists a g(|C|)-competitive algorithm for the Layered-MSP, where g is
a non-decreasing function. Then,
(i) there exists an O(g(1 + log ρ)) ordinal-competitive algorithm for the MSP, and
(ii) there exists an O(g(1 + ρ)) probability-competitive algorithm for the MSP.
Proof of Theorem 3. We observe that g(x) = 8⌈log(x + 1) + 1⌉ is non-decreasing, so we can apply
Lemma 25 using Algorithm 10 and Theorem 24.
In the following, let Alayer be a g(|C|)-competitive algorithm for the layered-MSP. Our algorithm
for Lemma 25 (i), depicted as Algorithm 11, first gets a sample from R with expected size n/2, and
constructs a partition C using the optimum of the sample. By sampling a set F over the remaining
elements it feeds Alayer with a layered matroid.
Algorithm 11 O(g(1 + log ρ)) ordinal-competitive algorithm
Input: Matroid M(R, I, ≻) in random order r1 , r2 , . . . , rn .
1: Let s ∼ Bin(n, 1/2) and compute OPT(Rs ) = {s(1), . . . , s(ℓ)}, where s(1) ≻ s(2) ≻ · · · ≻ s(ℓ).
2: Let C = {s(1), s(2), s(4), . . . , s(2k−1 )}, where k = ⌊log ℓ⌋ + 1.
3: Let t ∼ Bin(n − s, 1/2) and let F = {rs+1 , . . . , rs+t } be the next t elements from R \ Rs .
4: Return ALG = Alayer (M|R\Rs , F, C, ≻).
Proof of Lemma 25 (i). Let OPT = {f (1), . . . , f (ρ)} be such that f (1) ≻ f (2) ≻ · · · ≻ f (ρ).
Consider the function T : N → N given by T (0) = 0, T (i) = |{r ∈ R : r ≻ f (i)}| if i ∈ [1, ρ]
and T (i) = n if i > ρ. In particular, for i ∈ [1, ρ], T (i) is the number of elements in M that
are at least as high as the i-th element of OPT, so f (i) = r T (i) . Observe that for all k such that
T (i) ≤ k < T (i + 1) we have |OPT ∩ Rk | = i. In the following we study the expected number of
elements from Rk that the algorithm selects, so we can conclude using Lemma 5. If T (0) ≤ k < T (1)
it holds E[|ALG ∩ Rk |] = 0 = |OPT ∩ Rk |, so this case is done.
Let k ∈ N be such that T (1) ≤ k < T (8). Let f be the highest non-loop element in the value
order with f (1) ≻ f . With probability at least 1/4, it holds that f (1) ∈ R \ Rs and f ∈ Rs . In
this case, f ∈ OPT(Rs ), since f (1) = s(1), and the only non-loop element of C0 is f (1). Thus,
C0 = {f (1)} = OPT(R \ Rs ) ∩ C0 . Therefore,
Pr(C0 = {f (1)}) ≥ Pr(f (1) ∈ R \ Rs , f ∈ Rs ) ≥ 1/4.
8
9

The contraction of M = (R, I) by Q, M/Q, has ground set R−Q and a set I is independent if ρ(I∪Q)−ρ(Q) = |I|.
The restriction of M = (R, I) to Q, M|Q , has ground set Q and a set I is independent if I ∈ I and I ⊆ Q.

31

Since g is non-decreasing and |C| ≤ 1+log ℓ ≤ 1+log ρ, Algorithm Alayer is g(1+log ρ)-competitive.
Furthermore, the event C0 = {f (1)} depends only on steps 1 and 2 of the algorithm before executing
Alayer . It follows that
1
1
Pr(f (1) ∈ ALG|C0 = {f (1)}) = E[|ALG ∩ C0 | | C0 = {f (1)}]
4
4
1
1
≥
E[|OPT(R \ Rs ) ∩ C0 | | C0 = {f (1)}] =
.
4g(1 + log ρ)
4g(1 + log ρ)

Pr(f (1) ∈ ALG) ≥

Since |OPT ∩ Rk | ≤ 8, we conclude in this case that
E[|ALG ∩ Rk |] ≥ Pr(f (1) ∈ ALG) ≥

1
1
≥
|OPT ∩ Rk |.
4g(1 + log ρ)
32g(1 + log ρ)

Let j ≥ 3 and k be such that T (2j ) ≤ k < T (2j+1 ). We denote q = 2j−3 . Let Aj be the event where
|{f (1), . . . , f (2q)}∩R\Rs | ≥ q and Bj is the event where |{f (2q+1), . . . , f (6q)}∩Rs | ≥ 2q. We have
that Pr(Aj ∩ Bj ) ≥ 1/4, since in our algorithm the probability for an element to be sampled equals
the probability of not being sampled. Observe that any subset of elements strictly better than f (t)
has rank at most t − 1, and therefore f (2q)  s(2q). If Bj holds, then s(2j−2 ) = s(2q)  f (6q).
Since f (6q)  f (8q) = f (2j ), it follows that
j−3
[
i=0

j

Ci ⊆ {r ∈ R \ Rs : r  f (2j )} = RT (2 ) ∩ R \ Rs .

This implies that
j−3
i 1 h
[
1 h
T (2j )
Ci
| Aj ∩ Bj ≥ E ALG ∩
E[|ALG ∩ R |] ≥ E |ALG ∩ R
4
4
k

i=0

i
Aj ∩ Bj .

Furthermore, if Aj holds, then
OPT(R \ Rs ) ∩

j−3
[
i=0

Ci = |{f ∈ OPT ∩ R \ Rs : f  s(2q)}|
≥ |{f ∈ OPT ∩ R \ Rs : f  f (2q)}| ≥ q.

Since g is non-decreasing and |C| ≤ 1+log ℓ ≤ 1+log ρ, Algorithm Alayer is g(1+log ρ)-competitive.
Since events Aj and Bj depend only on the sampling at line 1 of the algorithm (before executing
Alayer ) and by using linearity of the expectation and the observation above we have that
j−3
[
1 h
Ci
E ALG ∩
4
i=0

i
Aj ∩ Bj ≥
≥

j−3
h
[
1
Ci
E OPT(R \ Rs ) ∩
4g(1 + log ρ)
i=0

Aj ∩ Bj

1
1
q≥
|OPT ∩ Rk |,
4g(1 + log ρ)
64g(1 + log ρ)

i

where the last inequality holds since |OPT ∩ Rk | ≤ 2j+1 = 16q. By using Lemma 5 we conclude
that the algorithm is O(g(1 + log ρ)) ordinal-competitive.
32

Algorithm 12 O(g(1 + ρ)) probability-competitive algorithm
Input: Matroid M(R, I, ≻) in random order r1 , r2 , . . . , rn .
1: Let s ∼ Bin(n, 1/2) and compute OPT(Rs ) = {s(1), . . . , s(ℓ)}, where s(1) ≻ s(2) ≻ · · · ≻ s(ℓ).
2: Let t ∼ Bin(n − s, 1/2) and let F = {rs+1 , . . . , rs+t } be the next t elements from R \ Rs .
3: Return ALG = Alayer (M|R+ , F ∩Rs+ , OPT(Rs ), ≻), where Rs+ = {r ∈ R\Rs : r ∈ OPT(Rs +r)}.
s
To prove Lemma 25 (ii), consider Algorithm 12 depicted above. Before the analysis, it will be
useful to consider the next process. Let (Xt )t∈N be a sequence of Bernoulli independent random
variables such that Pr(Xt = 0) = Pr(Xt = 1) = 1/2 for every t ∈ N. We create two sets V, W ⊆ R
iteratively using the following procedure.
Algorithm 13 Coupling procedure
Input: Matroid M(R, I, ≻).
1: Initialize V ← ∅, W ← ∅ and θ ← 0.
2: for i = 1 to n do
3:
if r i ∈ OPT(V + r i ) then
4:
θ ← θ + 1 and Yθ = Xi .
5:
if Yθ = 0 then
6:
V ← V + ri
7:
else W ← W + r i .
The value θ represents a counter on the elements that improve over the current set V . When
the counter is updated, we say that the element considered on that iteration is assigned coin Yθ .
Lemma 26. (V, W ) has the same distribution as (OPT(Rs ), Rs+ ) in Algorithm 12.
Proof. Let (Vi , Wi )ni=1 be the states of the coupling process at the end of each iteration. Let
Z = {r i : Xi = 0}. Observe that Z and the sample Rs of Algorithm 12 have the same distribution.
Since the coupling procedure checks from highest to lowest element, it follows that Vi = OPT(Z∩Ri )
for every i ∈ {1, . . . , n}, and therefore Vn = OPT(Z). To conclude the lemma it suffices to check
that Wn = {r ∈ R \ Z : r ∈ OPT(Z + r)}. In fact, it can be proven by induction that
Wi = {r ∈ Ri \ Z : r ∈ OPT(Vi + r)}
for every i ∈ {1, . . . , n}, and so the lemma follows, since Rn = R and Vn = OPT(Z).
Proof of Lemma 25 (ii). Thanks to Lemma 26 we assume that (OPT(Rs ), Rs+ ) is generated by the
process described in Algorithm 13. In what follows, fix f (j) = r T (j) ∈ OPT. We know that at step
T (j) of the coupling procedure, f (j) ∈ OPT(Rs + f (j)) no matter the trajectory of (Xt )t∈N . Let
θ be such that r T (j) is assigned coin Yθ , that is, Yθ = XT (j) . Then, with probability at least 1/8,
the event E defined as Yθ−1 = Yθ+1 = 0 and Yθ = 1, holds. If E happens, let s(h) be the element
of OPT(Rs ) who was assigned coin Yθ−1 . In particular, the element s(h + 1) is assigned coin Yθ+1 .
Thus,
Ch = {r ∈ Rs+ : s(h) ≻ r ≻ s(h + 1)} = {f (j)} = OPT(Rs+ ) ∩ Ch .

33

Therefore by using that the occurrence of E is decided before executing Alayer which is g(1 + ℓ) ≤
g(1 + ρ) competitive, we get that
1
Pr(f (j) ∈ ALG|E)
8
1
1
1
= E[|ALG ∩ Ch ||E] ≥
E[|OPT(Rs+ ) ∩ Ch ||E] =
,
8
8g(ρ + 1)
8g(ρ + 1)

Pr(f (j) ∈ ALG) ≥

and we conclude that Algorithm 12 is O(g(1 + ρ)) probability-competitive.

4.3

Comparison between ordinal measures

In this section we discuss about some incomparability results for the competitiveness measures
previously introduced. We show that an algorithm that is utility-competitive is not necessarily
competitive for the rest of the measures. In particular, we provide an instance where the O(log ρ)
utility-competitive algorithm by Babaioff, Immorlica and Kleinberg [5] has a poor competitiveness
for the other three. Regarding the notions of the ordinal MSP, we show that the intersection and
the ordinal measures are incomparable. More specifically, we show the existence of an algorithm
and an instance where it is arbitrarily close to 1 intersection-competitive, but have an unbounded
ordinal/probability-competitiveness. And on the other hand, we also show the existence of an algorithm and an instance where it is arbitrarily close to 1 ordinal-competitive, but have an unbounded
intersection/probability-competitiveness. Recall that probability is the strongest in the sense that
it implies competitiveness for all the other measures considered (see Lemma 6).
In the utility variant, the weight w(r) of an element is revealed to the algorithm when arrived.
Suppose for simplicity that the rank ρ of the matroid is known10 and that the weights the algorithm
sees are all different. In the above mentioned algorithm, called by the authors the Threshold Price
Algorithm (TPA), it is taken a sample Rs of s ∼ Bin(n, 1/2) elements11 and it records the top
weight w∗ of a non-loop12 element seen in Rs . It chooses uniformly at random a number τ in the
set {0, 1, 2, . . . , ⌈log2 ρ⌉}, and then it selects greedily any non-sampled element whose weight is at
least T = w∗ /2τ .
Theorem 27 (Babaioff et al. [5]). The algorithm TPA is O(log ρ) utility-competitive.
4.3.1

TPA is Ω(ρ) intersection, ordinal and probability-competitive

We show in this section that TPA is Ω(ρ)-competitive in the intersection, ordinal and probability
measures. We first revisit the proof by [5] for the O(log ρ) utility-competitiveness of TPA.
Proof of Theorem 27. Let OPT = {f (1), . . . , f (ρ)} be the optimal base such that w1 > w2 > · · · >
wρ , where wi = w(f (i)) for each i ∈ {1, . . . , ρ}. Suppose that f (1) ∈
/ Rs . Then, if the second
non-loop element of the matroid is sampled and if τ = 0, the element f (1) will be selected in the
second phase of TPA. Hence Pr(f (1) ∈ ALG) ≥ 1/4 · 1/(⌈log ρ⌉ + 1) = Ω(1/ log ρ).
10

This assumption can be removed by using standard arguments; we can set ρ equal to twice the rank of the
sampled part.
11
The original analysis uses half of n, but the analysis gets simpler if one uses Bin(n, 1/2) since one can assume
that each element is in the sample with probability 1/2 independent of the rest.
12
A loop in a matroid is an element that belongs to no basis.

34

Let B = {i ∈ {2, . . . , ρ} : wi ≥ w1 /ρ}, and let Ei be the event where f (1) ∈ Rs and wi /2 < T ≤
wi . For each i ∈ B, we have log(w1 /wi ) < log ρ and therefore Pr(Ei ) = 1/2·Pr(τ = ⌈log(w1 /wi )⌉) =
Ω(1/ log ρ). The random order assumption implies that in expectation (i − 1)/2 ≥ i/4 elements in
{f (2), . . . , f (i)} are non-sampled, hence the expected rank of the matroid restricted to non-sampled
elements of weight at least wi = w(f (i)) is Ω(i). Therefore, given i ∈ B and conditioned on Ei , the
algorithm selects Ω(i) elements of value at least wi /2. It follows that for each i ∈ B,


i
.
E[|ALG ∩ {r : w(r) ≥ wi /2}|] ≥ Pr(Ei )E[|ALG ∩ {r : w(r) ≥ wi /2}||Ei ] = Ω
log ρ
In addition, observe that the elements P
in OPT \ {f (i) : i ∈ B ∪ {1}} have total weight less than
w1 (ρ − |B| − 1)/ρ < w1 , and therefore 2 i∈B∪{1} wi ≥ w(OPT). Putting all together, we have
that the expected weight of the output is
ρ

1X
(wi − wi+1 )E[|ALG ∩ {r : w(r) ≥ wi /2}|]
2
i=1
 X

1
(wi − wi+1 ) · i
=Ω
log ρ
i∈B∪{1}


 X

1
1
=Ω
wi = Ω
w(OPT).
log ρ
log ρ

E[w(ALG)] ≥

i∈B∪{1}

We study in the following the competitiveness of TPA for the ordinal measures. Since probability is the strongest (Lemma 6), it is enough to check that TPA is Ω(ρ) ordinal and intersection
competitive. Let R = {r 1 , . . . , r n } with n = 2ρ3 . Consider the laminar family {Rn/2 , R}, where
Rn/2 = {r 1 , . . . , r n/2 }, and take the laminar matroid (R, I) where a set I ∈ I is independent if
|I ∩ Rn/2 | ≤ 1 and |I| ≤ ρ. In particular, the matroid rank is ρ. Given ε > 0, the weights are given
by w(r i ) = 8 − εi for i ∈ {1, . . . n/2}, and w(r i ) = 7 − εi for i ∈ {n/2 + 1, . . . , n}.
Observe that the optimal basis is given by OPT = {r 1 , r n/2+1 , . . . , r n/2+ρ−1 }. If we run TPA
on this instance, with probability p = 1 − 2−n/2 the top weight w∗ in the sample is from Rn/2 , and
thus, 7 < w∗ < 8. Let E be this event. No matter the value of T , the algorithm always select at
most ρ elements in the non-sampled part, and therefore
E[|ALG ∩ OPT|] = (1 − 2−n/2 )E[|ALG ∩ OPT||E] + 2−n/2 E[|ALG ∩ OPT||E]
3

≤ E[|ALG ∩ OPT||E] + ρ · 2−ρ ≤ E[|ALG ∩ OPT||E] + 1.

Conditional on E, we have that either T > 7 or T < 4. In the first case, TPA will select at
most one element, which would come from Rn/2 , and so |ALG ∩ OPT| ≤ 1. Otherwise, if T < 4,
the algorithm will select at most one element from Rn/2 and at most the first ρ non-sampled
elements from R \ Rn/2 . The expected number of elements in {r n/2+1 , . . . , r n/2+ρ−1 } appearing
in {rs+1 , . . . , rs+ρ }, that is the first ρ elements appearing after the sample, is (ρ − 1)ρ/n < 1. It
follows that E[|ALG ∩ OPT||E] is upper bounded by 2, and therefore E[|ALG ∩ OPT|] ≤ 3. The
discussion above implies as well that E[|ALG ∩ Rn/2+ρ−1 |] ≤ 3, and then TPA is Ω(ρ) intersection
and ordinal competitive. The conclusion for the ordinal case follows by using the characterization
for ordinal competitiveness in Lemma 5.

35

4.3.2

The ordinal and intersection measures are not comparable

We show in the following that there is no competitiveness dominance between the intersection and
the ordinal notions. Let m and M be two positive integers. Consider R = {r 1 , r 2 , . . . , r (M +1)m }
and let L be the partition of R given by
L=

m
[

i

{{r }} ∪

i=1

M
[

{{r jm+1 , . . . , r (j+1)m }}.

j=1

In particular, we consider the partition matroid Mm,M = (R, I) where I ∈ I if |I ∩ L| ≤ 1 for every
L ∈ L. The matroid rank is m + M . The algorithm we choose is greedy: we initialize ALG ← ∅,
and when an element r arrives it is selected if ALG + r ∈ I.

Lemma 28. Suppose M ≥ m2 . Then, the greedy algorithm over instance Mm,M is (1 + 1/m)
ordinal-competitive and Ω(m) intersection-competitive.

In fact, the ordinal competitiveness holds no matter what the value of M is. We adjust the
value of M in order to get a poor competitiveness for the intersection notion.
Proof of Lemma 28. The optimal base of Mm,M is the highest element of each part in L, that is,
OPT = {r 1 , r 2 , . . . , r m } ∪ {r jm+1 : j ∈ {1, . . . , M }}.

In particular, we have
(
k
|OPT ∩ Rk | =
m+j

if k ∈ {1, . . . , m},
if k ∈ {jm + 1, . . . , (j + 1)m} and j ∈ {1, . . . , M }.

Observe that an element r ∈ Q, with Q ∈ L, is selected by the algorithm if and only if r is the first
element of Q that arrives. Therefore, Pr(r i ∈ ALG) = 1 if i ∈ {1, . . . , m} and Pr(r i ∈ ALG) = 1/m
if i ∈ {m + 1, . . . , (m + 1)m}. It follows that E[|ALG ∩ Rk |] = k if k ∈ {1, . . . , m}. If k > m, then
k

E[|ALG ∩ R |] =

m
X
i=1

i

Pr(r ∈ ALG) +

k
X

i=m+1

Pr(r i ∈ ALG) = m +

1
(k − m).
m

Thus, when k ∈ {1, . . . , m}, we have |OPT ∩ Rk |/E[|ALG ∩ Rk |] = 1. Suppose k = jm + r with
j ≥ 1 and 0 ≤ r ≤ m. Then,
m+j
|OPT ∩ Rk |
=
1
k
E[|ALG ∩ R |]
m+ m
(k − m)
m−r
1
1
=1+ 2
≤1+
≤ ,
m + mj + r − m
m+j−1
m

and thus the greedy algorithm is (1 + 1/m) ordinal-competitive for Mm,M . In the first inequality
we used that φ(x) = (m − x)/(m2 + mj + x − m) is a decreasing function in the interval [0, m].
Observe that the competitiveness result holds no matter the value of M . It remains to study the
intersection competitiveness. By the observations above, we have that
m + m2
m+M
m
|OPT|
≥
=
≥ ,
1
E[|ALG ∩ OPT|]
m+m
2
m+ m ·M
and so the algorithm is at least Ω(m) intersection-competitive.
36

Although not mentioned explicitly in the proof, since Pr(r i ∈ ALG) = 1/m for i > m it follows
that the algorithm is m probability competitive for Mm,M , and for every M . In the following
we construct an instance for which the intersection competitiveness is close to 1, but the ordinal
competitiveness is poor. Let m be a positive integer and R = {r 1 , . . . , r 2m−1 }. Consider the
partition L given by

L = {r 1 , . . . , r m }, {r m+1 }, {r m+2 }, . . . , {r 2m−1 } .
Let Nm = (R, I) be the partition matroid where I ∈ I if |I ∩ L| ≤ 1 for every L ∈ L. The matroid
rank is m.

Lemma 29. The greedy algorithm over instance Nm is (1 + 1/m) intersection-competitive and
Ω(m) ordinal-competitive.
Proof. An element r ∈ Q, with Q ∈ L, is selected by the algorithm if and only if r is the first
element of Q that arrives. Therefore, Pr(r i ∈ ALG) = 1/m if i ∈ {1, . . . , m} and Pr(r i ∈ ALG) = 1
if i ∈ {m + 1, . . . , 2m − 1}. Since OPT = {r 1 , r m+1 , . . . , r 2m−1 },
1
|OPT ∩ R1 |
=
= 1/(1/m) = m,
1
1
E[|ALG ∩ R |]
Pr(r ∈ ALG)
hence the algorithm is Ω(m) ordinal-competitive. Finally, we have
m
1
|OPT|
=
≤1+ ,
E|ALG ∩ OPT|
1/m + m − 1
m
and we conclude that the greedy algorithm is (1 + 1/m) intersection-competitive over Nm .

References
[1] M. Ajtai, N. Megiddo, and O. Waarts. Improved Algorithms and Analysis for Secretary
Problems and Generalizations. SIAM Journal on Discrete Mathematics, 14(1):1–27, 2001.
[2] P. D. Azar, R. Kleinberg, and S. M. Weinberg. Prophet inequalities with limited information.
In Proc. of SODA 2014, pages 1358–1377, 2014.
[3] M. Babaioff, M. Dinitz, A. Gupta, N. Immorlica, and K. Talwar. Secretary Problems: Weights
and Discounts. In Proc. of SODA 2009, pages 1245–1254, 2009.
[4] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A knapsack secretary problem with
applications. In Proc. of APPROX-RANDOM 2007, volume 4627 of LNCS, pages 16–28, 2007.
[5] M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. of SODA 2007, pages 434–443, 2007.
[6] S. Barman, S. Umboh, S. Chawla, and D. L. Malec. Secretary problems with convex costs. In
Proc. of ICALP 2012, volume 7391 of LNCS, pages 75–87, 2012.
[7] M. Bateni, M. Hajiaghayi, and M. Zadimoghaddam. Submodular secretary problem and extensions. ACM Transactions on Algorithms, 9(4):1–23, 2013.
37

[8] M. Beckmann. Dynamic programming and the secretary problem. Computers & Mathematics
with Applications, 19(11):25–28, 1990.
[9] F. T. Bruss. Sum the odds to one and stop. The Annals of Probability, 28(3):1384–1391, 2000.
[10] N. Buchbinder, K. Jain, and M. Singh. Secretary Problems via Linear Programming. Mathematics of Operations Research, 39(1):190–206, 2014.
[11] S. Chakraborty and O. Lachish. Improved Competitive Ratio for the Matroid Secretary Problem. In Proc. of SODA 2012, pages 1702–1712, 2012.
[12] T.-H. H. Chan, F. Chen, and S. H.-C. Jiang. Revealing Optimal Thresholds for Generalized
Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite KMatching with Random Arrival Order. In Proc. of SODA 2015, pages 1169–1188, 2015.
[13] N. B. Dimitrov and C. G. Plaxton. Competitive Weighted Matching in Transversal Matroids.
Algorithmica, 62(1-2):333–348, 2012.
[14] M. Dinitz and G. Kortsarz. Matroid Secretary for Regular and Decomposable Matroids. SIAM
Journal on Computing, 43(5):1807–1830, 2014.
[15] P. Dütting and R. Kleinberg. Polymatroid prophet inequalities. In Proc. of ESA 2015, volume
9294 of LNCS, pages 437–449, 2015.
[16] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math.
Dokl, 4:627–629, 1963.
[17] J. Edmonds and D. Fulkerson. Transversals and matroid partition. Journal of Research of the
National Bureau of Standards Section B Mathematics and Mathematical Physics, 69B(3):147–
153, 1965.
[18] M. Feldman, J. Naor, and R. Schwartz. Improved competitive ratios for submodular secretary
problems (extended abstract). In APPROX-RANDOM, volume 6845 of LNCS, pages 218–229,
2011.
[19] M. Feldman, O. Svensson, and R. Zenklusen. A Simple O (log log(rank)) -Competitive Algorithm for the Matroid Secretary Problem. In Proc. of SODA 2015, pages 1189–1201, 2015.
[20] M. Feldman and R. Zenklusen. The submodular secretary problem goes linear. In Proc. of
FOCS 2015, pages 486–505, 2015.
[21] T. S. Ferguson. Who Solved the Secretary Problem? Statistical Science, 4(3):282–289, 1989.
[22] J. P. Gilbert and F. Mosteller. Recognizing the Maximum of a Sequence. Journal of the
American Statistical Association, 61(313):35, 1966.
[23] M. Hoefer and B. Kodric. Combinatorial Secretary Problems with Ordinal Information.
In I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, editors, Proc. of ICALP 2017,
volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 133:1–133:14,
Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

38

[24] S. Im and Y. Wang. Secretary Problems: Laminar Matroid and Interval Scheduling. In Proc.
of SODA 2011, pages 1265–1274, 2011.
[25] P. Jaillet, J. A. Soto, and R. Zenklusen. Advances on Matroid Secretary Problems: Free Order
Model and Laminar Case. In Proc. of IPCO 2013, volume 7801 of LNCS, pages 254–265, 2013.
[26] P. Jaillet, J. A. Soto, and R. Zenklusen. Advances on Matroid Secretary Problems: Free Order
Model and Laminar Case (Full version). http://arxiv.org/abs/1207.1333v2, 2014.
[27] M. Janata. Matroids induced by packing subgraphs. SIAM J. Discrete Math., 18(3):525–541,
2005.
[28] T. Kesselheim, R. Kleinberg, and R. Niazadeh. Secretary Problems with Non-Uniform Arrival
Order. In Proc. of STOC 2015, pages 879–888, 2015.
[29] T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. An Optimal Online Algorithm for
Weighted Bipartite Matching and Extensions to Combinatorial Auctions. In Proc. of ESA
2013, volume 8125 of LNCS, pages 589–600, 2013.
[30] T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. Primal beats dual on online packing
LPs in the random-order model. In Proc. of STOC 2014, pages 303–312, 2014.
[31] R. Kleinberg. A Multiple-Choice Secretary Algorithm with Applications to Online Auctions.
In Proc. of SODA 2005, pages 630–631, 2005.
[32] R. Kleinberg and S. M. Weinberg. Matroid prophet inequalities. In Proc. of STOC 2012, pages
123–136, 2012.
[33] N. Korula and M. Pál. Algorithms for Secretary Problems on Graphs and Hypergraphs. In
Proc. of ICALP 2009, volume 5556 of LNCS, pages 508–520, 2009.
[34] O. Lachish. O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. In Proc.
of FOCS, pages 326–335, 2014.
[35] G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4(4):331–340, 1970.
[36] D. V. Lindley. Dynamic Programming and Decision Theory. Applied Statistics, 10(1):39–51,
1961.
[37] M. Loebl and S. Poljak. On matroids induced by packing subgraphs. Journal of Combinatorial
Theory, Series B, 44(3):338–354, 1988.
[38] M. Loréa. Hypergraphes et matroı̈des. Cahiers Centre Etud. Rech. Oper, 17:289–291, 1975.
[39] T. Ma, B. Tang, and Y. Wang. The Simulated Greedy Algorithm for Several Submodular
Matroid Secretary Problems. Theory of Computing Systems, 58(4):681–706, 2016.
[40] M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.

39

[41] S. Oveis Gharan and J. Vondrák. On Variants of the Matroid Secretary Problem. Algorithmica,
67(4):472–497, 2013.
[42] A. Rubinstein. Beyond matroids: secretary problem and prophet inequality with general
constraints. In Proc. of STOC 2016, pages 324–332, 2016.
[43] A. Rubinstein and S. Singla. Combinatorial prophet inequalities. In Proc. of SODA 2017,
pages 1671–1687. SIAM, 2017.
[44] J. A. Soto. Matroid Secretary Problem in the Random-Assignment Model. SIAM Journal on
Computing, 42(1):178–211, 2013.
[45] I. Streinu and L. Theran. Natural realizations of sparsity matroids. Ars Mathematica Contemporanea, 4(1):141–151, 2011.
[46] T. S. Tay. Rigidity of multi-graphs. I. Linking rigid bodies in n-space. Journal of Combinatorial
Theory, Series B, 36(1):95–112, 1984.
[47] W. Whiteley. Some matroids from discrete applied geometry. Contemporary Mathematics,
197:171–311, 1996.
[48] T. Zaslavsky. Frame Matroids and Biased Graphs. European Journal of Combinatorics,
15(3):303–307, 1994.

40

