Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
The best-known conjecture in the context of matroid secretary problems claims the existence of an O(1)-approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adv...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86895 https://orcid.org/0000-0002-8585-6566 |
| _version_ | 1826197733526994944 |
|---|---|
| author | Jaillet, Patrick Soto, Jose A. Zenklusen, Rico |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jaillet, Patrick Soto, Jose A. Zenklusen, Rico |
| author_sort | Jaillet, Patrick |
| collection | MIT |
| description | The best-known conjecture in the context of matroid secretary problems claims the existence of an O(1)-approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adversarial but uniformly at random [20,18]. However, so far, no variant of the matroid secretary problem with adversarial weight assignment is known that admits an O(1)-approximation. We address this point by presenting a 9-approximation for the free order model, a model suggested shortly after the introduction of the matroid secretary problem, and for which no O(1)-approximation was known so far. The free order model is a relaxed version of the original matroid secretary problem, with the only difference that one can choose the order in which secretaries are interviewed.
Furthermore, we consider the classical matroid secretary problem for the special case of laminar matroids. Only recently, a O(1)-approximation has been found for this case, using a clever but rather involved method and analysis [12] that leads to a 16000/3-approximation. This is arguably the most involved special case of the matroid secretary problem for which an O(1)-approximation is known. We present a considerably simpler and stronger 3√3e ≈ 14.12 -approximation, based on reducing the problem to a matroid secretary problem on a partition matroid. |
| first_indexed | 2024-09-23T10:52:18Z |
| format | Article |
| id | mit-1721.1/86895 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:52:18Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/868952022-09-30T23:34:45Z Advances on Matroid Secretary Problems: Free Order Model and Laminar Case Jaillet, Patrick Soto, Jose A. Zenklusen, Rico Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jaillet, Patrick The best-known conjecture in the context of matroid secretary problems claims the existence of an O(1)-approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adversarial but uniformly at random [20,18]. However, so far, no variant of the matroid secretary problem with adversarial weight assignment is known that admits an O(1)-approximation. We address this point by presenting a 9-approximation for the free order model, a model suggested shortly after the introduction of the matroid secretary problem, and for which no O(1)-approximation was known so far. The free order model is a relaxed version of the original matroid secretary problem, with the only difference that one can choose the order in which secretaries are interviewed. Furthermore, we consider the classical matroid secretary problem for the special case of laminar matroids. Only recently, a O(1)-approximation has been found for this case, using a clever but rather involved method and analysis [12] that leads to a 16000/3-approximation. This is arguably the most involved special case of the matroid secretary problem for which an O(1)-approximation is known. We present a considerably simpler and stronger 3√3e ≈ 14.12 -approximation, based on reducing the problem to a matroid secretary problem on a partition matroid. National Science Foundation (U.S.) (Grant 1029603) United States. Office of Naval Research (Grant N00014-12-1-0033) United States. Office of Naval Research (Grant N00014-09-1-0326) 2014-05-09T14:17:55Z 2014-05-09T14:17:55Z 2013-03 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-36693-2 978-3-642-36694-9 0302-9743 1611-3349 http://hdl.handle.net/1721.1/86895 Jaillet, Patrick, Jose A. Soto, and Rico Zenklusen. “Advances on Matroid Secretary Problems: Free Order Model and Laminar Case.” Lecture Notes in Computer Science (2013): 254–265. https://orcid.org/0000-0002-8585-6566 en_US http://dx.doi.org/10.1007/978-3-642-36694-9_22 Integer Programming and Combinatorial Optimization Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Jaillet, Patrick Soto, Jose A. Zenklusen, Rico Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title_full | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title_fullStr | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title_full_unstemmed | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title_short | Advances on Matroid Secretary Problems: Free Order Model and Laminar Case |
| title_sort | advances on matroid secretary problems free order model and laminar case |
| url | http://hdl.handle.net/1721.1/86895 https://orcid.org/0000-0002-8585-6566 |
| work_keys_str_mv | AT jailletpatrick advancesonmatroidsecretaryproblemsfreeordermodelandlaminarcase AT sotojosea advancesonmatroidsecretaryproblemsfreeordermodelandlaminarcase AT zenklusenrico advancesonmatroidsecretaryproblemsfreeordermodelandlaminarcase |