Optimization and Uncertainty - Summer 2025

Logbook Optimization and Uncertainty - Summer 2025

Lecture 11 -- 13.05.2025:
Testing, k-TestMax, testing a box = refining the support region in which realization is located, testing vs. probing, testing policy for the IID case that obtains at least 1-1/e^1/4-o(1) of the expected reward of the optimal probing policy
Literature:
- Notes: Section 4.2
- M. Hoefer, K. Schewior, D. Schmand. Stochastic Probing with Increasing Precision. SIAM J. Discrete Mathematics 38(1):148-169, 2024.

Lecture 10 -- 12.05.2025:
Probing, k-ProbeMax, non-adaptive and adaptive policies, adaptivity gap, adaptivity gap for k-ProbeMax is at most 8, bounding the optimum using a linear program, deriving a non-adaptive policy from the LP optimum.
Literature:
- Notes: Section 4.1
- A. Asadpour, H. Nazerzadeh. Maximizing Stochastic Monotone Submodular Functions. Management Science 62(8):2374-2391, 2016.

Lecture 9 -- 06.05.2025:
Online independent set and the interval scheduling problem, prophet interval scheduling, 4-competitive algorithm, proof of the competitive ratio. Secretary independent set with random-order arrival, 8-competitive algorithm, proof by adjusting the arguments for the prophet case. Extensions to more general graphs (bounded inductive independence number) and graph sampling approaches
Literature:
- Notes: Sections 3.4.1, 3.4.2
- O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.

Lecture 8 -- 05.05.2025:
Yao's principle, given any input distribution, the best deterministic algorithm for that distribution performs better than any randomized algorithm on worst-case input, lower bound of Ω(n) on the competitive ratio of any randomized algorithm for OnlineMax. Online Independent Set, interval scheduling, lower bound Ω(n) on the competitive ratio, Prophet Interval Scheduling, 4-competitive algorithm.
Literature:
- Notes: Sections 3.3, 3.4, 3.4.1
- A. C.-C. Yao. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977.
- O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.

Lecture 7 -- 29.04.2025:
Examples for finite-time MDPs and optimal policies. SkiRental: Buy only on the first open day when there are at least ⌊((B-1)/q)+2⌋ days remaining; Prophet: accept any person as soon as it has more value than the expected value obtained by the optimal policy in the subsequent rounds.
Literature:
- Notes: Section 3.2.2

Lecture 6 -- 28.04.2025:
PrizeCollection problem, definition Markov decision process (MDP), optimal policy π^* for finite time horizon, existence of π^* that is Markovian, computation via a dynamic program (DP), example DP for PrizeCollection, alternative characterization of optimal policy: Open envelopes in non-increasing order of v_iq_i/(1-q_i)
Literature:
- Notes: Sections 3.2, 3.2.1, 3.2.2

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.