Ort: Heidelberg
Ort: TU Berlin
Ort: TU Braunschweig
Ort: Les Diablerets, Switzerland
Doignon proved a discrete version of Helly's theorem claiming that a finite family of convex sets in R^n intersects in an integral point if every subfamily of size at most 2^n does so. Motivated by applications in integer programming, Aliev et al. recently obtained a quantitative version of this result, which guarantees that a finite family of convex sets intersects in k integral points whenever every subfamily of size at most c_n(k) does so. The best current upper bound on the minimal such constant c_n(k) grows linearly with the parameter k. Based on a connection to the number of boundary integral points in strictly convex sets, we show that the asymptotic behavior of c_n(k) is sublinear in dimension two and we determine the exact value of c_n(k) for k at most four. ------
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Friedrich-Schiller-Universität, Jena
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar Room, Arnimallee 2, FU Berlin
The conference will celebrate the 60th birthdays in 2015 of Karoly Bezdek (University of Calgary, Canada and University of Pannonia, Hungary) and Egon Schulte (Northeastern University, USA). The theme of the conference will be “Geometry and Symmetry”, with emphasis on recent progress on aspects of discrete geometry in which Egon and Karoly have made remarkable contributions. The program of the conference will consist of invited lectures and contributed talks.
Ort: Veszprém, Hungary
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Arnimallee 6, FU Berlin
Ort: @BMS Loft Urania
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar Room, Arnimallee 2, FU Berlin
Lecture - 14:15 Tobias Friedrich - HPI, Universität Potsdam Distributed Processes on Scale-Free Networks Abstract: The node degrees of large real-world networks often follow a power-law distribution. Such scale-free networks can be social networks, internet topologies, the web graph, power grids, or many other networks from literally hundreds of domains. The talk will introduce three mathematical models of scale-free networks (preferential attachment graphs, Chung-Lu graphs, hyperbolic random graphs) and analyze some of their properties. We then study three distributed processes and algorithms on these network models (rumor spreading, load balancing, de-anonymization) and present several open problems. The talk assumes no prior knowledge about scale-free networks or distributed computing. Colloquium - 16:00 Fidaa Abed - Technische Universität Berlin Optimal Coordination Mechanisms for Multi-Job Scheduling Games Abstract: We consider the unrelated machine scheduling game in which players control subsets of jobs. Each player's objective is to minimize the weighted sum of completion time of her jobs, while the social cost is the sum of players' costs. The goal is to design simple processing policies in the machines with small coordination ratio, i.e., the implied equilibria are within a small factor of the optimal schedule. We work with a weaker equilibrium concept that includes that of Nash. We first prove that if machines order jobs according to their processing time to weight ratio, a.k.a. Smith-rule, then the coordination ratio is at most 4, moreover this is best possible among nonpreemptive policies. Then we establish our main result. We design a preemptive policy, externality, that extends Smith-rule by adding extra delays on the jobs accounting for the negative externality they impose on other players.. For this policy we prove that the coordination ratio is 1+ φ ≈ 2.618, and complement this result by proving that this ratio is best possible even if we allow for randomization or full information. Finally, we establish that this externality policy induces a potential game and that an ε-equilibrium can be found in polynomial time. An interesting consequence of our results is that an ε-local optima of $R|\,|\sum w_jC_j$ for the jump (a.k.a. move) neighborhood can be found in polynomial time and are within a factor of 2.618 of the optimal solution. The latter constitutes the first direct application of purely game-theoretic ideas to the analysis of a well studied local search heuristic.
Ort: @TU MA 041
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Urania Berlin, BMS Lounge
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: @TU MA 041
Ort: FU Berlin
Ort: BMS Loft in Urania
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: BMS Loft in Urania
Ort: @TU MA 041
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar room in the Villa, Arnimallee 2, 14195 Berlin
Ort: TU Berlin, Audimax, Straße des 17. Juni 135
Ort: @BMS Loft in Urania
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar room in the Villa, Arnimallee 2, 14195 Berlin
Ort: Jerusalem
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar room in the Villa, Arnimallee 2, 14195 Berlin
Ort: Freie Universität Berlin, Takustr, 9, 14195 Berlin, room: 005
Ort: Urania Berlin, BMS Lounge, An der Urania 17, 10787 BErlin
Ort: @BMS Loft in Urania
Ort: Seminar Room, Arnimallee 2, FU Berlin
Ort: Seminar room in the Villa, Arnimallee 2, 14195 Berlin
Ort: TU Dresden
Ort: Seoul, Korea
Ort: Uni Tübingen, Mathematik, N14
Ort: Urania Berlin
Ort: FU Berlin/Seminaris Conference Center
Ort: Cortona, Italy
Ort: Döllnsee
Ort: Döllnsee
Ort: Budapest
Ort: Moscow
Ort: Stockholm
Ort: FU Berlin
Ort: Castle Theatre, Potsdam-Sanssouci, Neues Palais
Ort: ZIB Berlin
Ort: ZIB Berlin
Ort: FU Berlin, Henry Ford Bau
Ort: Tu Berlin, Lichthof