Optimization and Uncertainty - Summer 2025

Logbook Optimization and Uncertainty - Summer 2025

Lecture 5 -- 22.04.2025:
OnlineMax with independent distributions, prophet inequalities in the general case, 2-competitive, tightness example; prophet inequality in the identical case, 1.58-competitive, discussion of improved approaches
Literature:
- Notes: Section 3.1
- J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld. Recent developments in prophet inequalities. SIGecom Exchanges 17(1):61–70, 2018
- E. Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability 12(4):1213–1216, 1984.

Lecture 4 -- 15.04.2025:
Item Allocation Problem, at least b ≥ 1 copies per item, bundles of size at most d, optimal fractional solution via linear programming, extension of the secretary algorithm is O(d^1/b)-competitive.
Literature:
- Notes: Section 2.4
- T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.

Lecture 3 -- 14.04.2025:
Stochastic concepts and tools, probability distributions, events, independence, conditional probabilities, law of total probability. Random variables, expectation, linearity of expectation. Concentration: Markov inequality, Chernoff bounds.
Literature:
- Notes: Appendix A
- Linearity of Expectation
- Markov and Chebyshev Inequalities
- Chernoff bounds

Lecture 2 -- 08.04.2025:
Secretary problem, e+o(1)-competitive algorithm, proof of the ratio. Max-weight bipartite matching, motivation via sponsored search, secretary matching problem, extension of the standard algorithm is e+o(1)-competitive. Main proof steps: expected value of random selected edge in round t is at least v(M^*)/n, probability to accept any such edge is s/(t-1).
Literature:
- Notes: Sections 2.2, 2.3
- T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.

Lecture 1 -- 07.04.2025:
(1) Organization and overview.
(2) Fundamentals in online algorithms: Competitive ratio, deterministic and randomized algorithms, randomization in the input.
(3) OnlineMax problem, lower bound Ω(n) on the competitive ratio. Secretary problem = OnlineMax with random-order arrival, e+o(1)-competitive algorithm.
Literature:
- Notes: Chapter 1, Sections 2, 2.1, 2.2
- Given its huge popularity, there are many surveys on the secretary problem. Here is a rather classic one:
  P.R. Freeman. The Secretary Problem and Its Extensions: A Review. Int. Stat. Rev., Vol. 51(2):189-206, 1983.