Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-moritz-buchem-maastricht-michelle-sweering-cwi-2-phd-talks
- Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- 2021-03-25T16:00:00+01:00
- 2021-03-25T17:00:00+01:00
- When Mar 25, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Moritz Buchem (Maastricht) + Michelle Sweering (CWI), 2 PhD talks
Title:
Moritz Buchem: Additive Approximation Schemes for Load Balancing problems
Michelle Sweering: On Breaking k-Trusses
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Additive Approximation Schemes for Load Balancing problems" (Moritz Buchem):
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.
This is joint work together with Lars Rohwedder (EPFL), Tjark Vredeveld (UM) and Andreas Wiese (UChile).
Video of the talk of Moritz Buchem:
Slides of the talk of Moritz Buchem:
Abstract of "On Breaking k-Trusses" (Michelle Sweering):
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.
Video of the talk of Michelle Sweering:
Slides of the talk of Michelle Sweering: