Dutch Seminar on Optimization (online series) with Moritz Buchem (Maastricht) + Michelle Sweering (CWI)

Everyone is welcome to attend the Dutch Seminar on Optimization (online series) with: Moritz Buchem: Additive Approximation Schemes for Load Balancing problems and Michelle Sweering: Breaking k-Trusses. All information can be found on the website: https://portals.project.cwi.nl/dutch-optimization-seminar/events/seminar-moritz-buchem-maastricht-michelle-sweering-cwi-2-phd-talks

Everyone is welcome to attend the Dutch Seminar on Optimization (online series) with:

Moritz Buchem: Additive Approximation Schemes for Load Balancing problem. Abstract:  We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most  εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.

Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search  algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.

Michelle Sweering: Breaking k-Trusses. Abstract: This talk is about breaking communities in networks, specifically k-trusses.
A subgraph H of G is a k-truss if each edge of H is contained in at least k-2 triangles in H.
We discuss how to break k-trusses by deleting as few edges as possible.
Since the problem of breaking k-trusses is NP-hard and even hard to approximate, we also give various heuristics.