BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T013749Z
UID:Seminar-dept-435@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20170321T130000
DTEND:20170321T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Andreas Toennis: Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions\n\nThe Temp Secretary Problem was recently introduced by Fiat et al. It is a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. We present a simple online algorithm with improved performance guarantees for cases already considered by Fiat et al. and give competitive ratios for new generalizations of the problem. In the classical\n\nsetting, where candidates have identical contract durations gamma << 1 and we are allowed to hire up to B candidates simultaneously, our algorithm is (1/2 − O(sqrt(gamma)))-competitive. For large B, the bound improves to 1 − O (1/sqrt(B)) − O(sqrt(gamma)).\n\n\n\nFurthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of 1 − O(sqrt((1+log d+log(B))/B)) − O(sqrt(gamma)), where d is the\n\nsparsity of the constraint matrix and B is generalized to the capacity ratio of linear constraints. Additionally we extend the problem towards arbitrary hiring durations.\n\n\n\nOur algorithmic approach is a relaxation that aggregates all temporal constraints into a non-temporal constraint. Then we apply a linear scaling algorithm that, on every arrival, computes a tentative solution on the input that is known up to this point. This tentative solution uses the non-temporal, relaxed constraints scaled down linearly by the amount of time that has already passed.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=435
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR