Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-celine-swennenhuis-eindhoven-sophie-huiberts-cwi-2-phd-talks
- Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- 2021-05-27T16:00:00+02:00
- 2021-05-27T17:00:00+02:00
- When May 27, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
-
Add event to calendar
iCal
Speaker: Céline Swennenhuis (TU Eindhoven) + Sophie Huiberts (CWI)
Title:
Céline Swennenhuis: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins
Sophie Huiberts: Combinatorial Diameter of Random Polytopes
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins" (Céline Swennenhuis):
Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time algorithm for Bin Packing. In this paper we show that for every m there exists a constant s_m > 0 such that an instance of Bin Packing with m bins can be solved in O((2-s_m)^n) time.
Video of the talk of Céline Swennenhuis:
Slides of the talk of Céline Swennenhuis:
Abstract of "Combinatorial Diameter of Random Polytopes" (Sophie Huiberts):
The combinatorial diameter of a polytope is the maximum shortest path between any two vertices of the polytope, in the graph consisting of that polytope's vertices and edges. This diameter is closely related to the simplex method for linear programming and has been studied since the 1950's, when Hirsch asked in a letter to Dantzig whether the combinatorial diameter of a polytope in R^n with m facets has diameter at most m-n.
In this paper we study random polytopes, either the intersection of random halfspaces or the convex hull of random vectors, chosen from the unit sphere. In the first case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (4√2)^n m^1/(n-1)) with high probability up to logarithmic factors. In the second case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (√2)^n m^1/(n-1)) with high probability up to logarithmic factors.
Video of the talk of Sophie Huiberts:
Notes of the talk of Sophie Huiberts, the website with polytopes, and a nice twitter abstract: