Skip to main content

2013 | OriginalPaper | Buchkapitel

Advances on Matroid Secretary Problems: Free Order Model and Laminar Case

verfasst von : Patrick Jaillet, José A. Soto, Rico Zenklusen

Erschienen in: Integer Programming and Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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\sqrt{3}e\approx 14.12$

-approximation, based on reducing the problem to a matroid secretary problem on a partition matroid.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
verfasst von
Patrick Jaillet
José A. Soto
Rico Zenklusen
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-36694-9_22