This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
Related publications (52)
Please note that this is not a complete list of this person’s publications. It includes only semantically relevant works. For a full list, please refer to Infoscience.
We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially.
The trivial greedy algorithm is (2 — o (1))-competitive, which is optimal for graphs of low maximum degree, Δ = O (log n) [BNMN IPL’92]. Numerous online edg ...
Society for Industrial and Applied Mathematics2025
In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowe ...
For any 𝜀 > 0, we prove that 𝑘-Dimensional Matching is hard to approximate within a factor of 𝑘/(12+𝜀) for large 𝑘 unless NP ⊆ BPP. Listed in Karp’s 21 NP-complete problems, 𝑘-Dimensional Matching is a benchmark computational complexity problem which we fi ...
