2022. 09. 12. 14:15 - 2022. 09. 12. 15:45
ELTE TTK Déli tömb 3.517
-
-
-
-
Esemény típusa:
szeminárium
Szervezés:
Külsős
-
Leírás
EGERVÁRY SZEMINÁRIUM
Abstract: In min-max symmetric submodular k-partitioning for fixed k,
the input is a symmetric submodular function given via an evaluation
oracle and the goal is to partition the ground set into k non-empty
parts V_1, V_2, …, V_k in order to minimize max_{i in [k]} f(V_i). I
will show a deterministic polynomial time algorithm to solve this
problem.
Based on joint work with Chandra Chekuri.