1 of 14

Laminar Matroid Secretary: Greedy Strikes Back

Zhiyi Huang 1, Zahra Parsaeian 2, Zixuan Zhu 1�

1 University of Hong Kong

​

2 University of Freiburg

2 of 14

Classic Secretary Problem

Decision maker

 

known

hidden information

irrevocable decision of acceptance or rejection

weight = 80

 

arrive online in a random order

weight = 60

weight = 78

3 of 14

Dynkin’s Algorithm

 

rejection

 

 

 

 

 

 

 

 

 

 

 

 

4 of 14

Matroids

 

 

 

 

 

  • A feasible set with a maximum total weight is denoted as OPT.

 

 

 

 

 

 

 

  • OPT can be found efficiently using Greedy Algorithm.

 

 

 

 

 

 

 

a finite set of elements

(ground set)

 

5 of 14

Matroid Secretary Problem

  • Elements arrive online.

 

 

 

 

 

  • Selected elements (ALG) must be feasible.

 

6 of 14

Laminar Matroids

 

 

1, 2, 3, 4, 5, 6, 7

 

1, 4, 5, 6

3,7

1, 5

4, 6

 

 

 

 

 

7

7

6

6

6

3

3

5

5

5

 

WLOG, capacities are strictly decreasing �from root to leaf.

 

4

4

4

7 of 14

Previous Results

 

 

 

  • [MTW16]: 9.6 (greedy-type algorithm)

Our Contribution: the simple greedy algorithm is 4.75-competitive.

8 of 14

Continuous Time Model

Continuous time model: each element arrives independently and uniformly between 0 and 1.

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.06

0.17

0.41

0.72

0.95

9 of 14

Greedy Algorithm

 

rejection

 

1

 

 

 

 

10 of 14

Competitive Analysis

 

 

 

 

 

 

 

1

 

 

 

rejected

 

 

 

 

 

 

 

 

 

 

 

 

11 of 14

Qualified Elements

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12 of 14

Count Qualified Elements

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

13 of 14

4.75-Competitiveness

 

 

 

union bound over all possible capacities

(capacities along a path are distinct!)

 

 

 

 

 

 

 

 

14 of 14

Thanks for your attention!