Abstract:\u00a0<\/strong><\/p>\n Secretary problems constitute a classical setting of online In this talk, I will introduce secretary problems, describe some <\/p>\n Venue:<\/strong> John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor<\/p>\n Vasilis Livanos<\/p>\n","protected":false},"author":129,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-696","post","type-post","status-publish","format-standard","hentry","category-past-seminar"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/users\/129"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/comments?post=696"}],"version-history":[{"count":3,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/696\/revisions"}],"predecessor-version":[{"id":702,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/696\/revisions\/702"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/media?parent=696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/categories?post=696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/tags?post=696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\ndecision-making, where discrete elements arrive in uniformly random
\norder, reveal their weight, and must be accepted or rejected
\nirrevocably, with the aim of maximizing a given function over the
\nselected set. In the most general form of the problem, we are given a
\ncombinatorial feasibility constraint (e.g. a matroid) and the selected
\nset has to be feasible with respect to that constraint. In such
\nproblems, the objective is to design algorithms which guarantee a
\nmultiplicative factor approximation with respect to the optimal feasible
\nset if we knew the weights of the elements in advance. By far the most
\nimportant open problem in this area is the Matroid Secretary conjecture,
\nwhich states that there exists a constant-factor approximation algorithm
\nfor every given matroid, and has been open for almost two decades now.<\/p>\n
\nstandard ideas and approaches for them, as well as present what is
\nprobably my favourite algorithm of all time: Korula and Pal’s
\n1\/(2e)-approximate algorithm for the graphic matroid setting (i.e.
\nselecting an acyclic set of edges in an undirected graph where the
\nweights of the edges is revealed online in uniformly random order).
\nLater on, if time permits, I will present some recent progress on
\nalgorithms for the general Matroid Secretary conjecture. This talk will
\nbe partly based on joint work with Krist\u00f3f B\u00e9rczi, Jos\u00e9 Soto and Victor
\nVerdugo that appeared in IPCO 2025.<\/p>\n