Universität Bonn

Rigidity Workshop


October 5-9, 2015

HIM Lecture Hall,  Poppelsdorfer Allee 45

Organizers: 

Satoru Iwata, Tibor Jordán, Jan Vondrák

Topics: Rigidity, Submodularity, Discrete Convexity


Schedule

Monday, October 5

9:00 - 9:30 Registration & Welcome coffee
9:30 - 9:40 Opening remarks
9:40 - 10:40 Seffi Naor: Recent Results on Maximizing Submodular Functions
10:40 - 11:00 Coffee break
11:00 - 12:00 Shin-ichi Tanigawa: Sufficient Conditions for Unique Graph Realizations
12:00 - 15:00 Lunch break & Discussions
15:00 - 15:30 Yuval Filmus: Monotone Submodular Optimization over a Matroid
15:30 - 16:00 Niv Buchbinder: Deterministic Algorithms for Submodular Maximization Problems
16:00 - 16:30 Tea and cake
16:30 - 17:00 Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige-Wolfe Algorithm
17:00 - 17:30 Satoru Fujishige: Combinatorial Polynomial Algorithms for Skew-bisubmodular Function Minimization
afterwards Reception

Tuesday, October 6

9:30 - 10:30 Kazuo Murota: Extensions and Ramifications of Discrete Convexity Concepts
10:30 - 11:00 Group photo & Coffee break
11:00 - 12:00 Bill Jackson: Generic Rigidity of Point-Line Frameworks
12:00 - 15:00 Lunch break & Discussions
15:00 - 15:30 Rico Zenklusen: The Submodular Secretary Problem Goes Linear
15:30 - 16:00 Kent Quanrad: Streaming Algorithms for Submodular Function Maximization
16:00 - 16:30 Tea and cake
16:30 - 17:00 Akiyoshi Shioura: Analysis of L-convex Function Minimization Algorithms and Application to Auction Theory
17:00 - 17:30 Tom McCormick: Discrete Convexity in Supply Chain Models

Wednesday, October 7

9:30 - 10:30 Uriel Feige: Optimization with Uniform Size Queries
10:30 - 11:00 Coffee break
11:00 - 12:00 Yin Tat Lee & Aaron Sidford: Faster Cutting Plane Methods and Improved Running Times for Submodular Function Minimization
12:00 - 16:00 Lunch break & Discussions
16:00 - 16:30 Tea and cake
16:30 - 17:00 Louis Theran: Rigidity of Random Graphs in Higher Dimensions
17:00 - 17:30 Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection

Thursday, October 8

9:30 - 10:30 András Frank: Non-TDI Optimization with Supermodular Functions
10:30 - 11:00 Coffee break
11:00 - 12:00 Bernd Schulze: Characterizing Minimally Flat Symmetric Hypergraphs
12:00 - 15:00 Lunch break & Discussions
15:00 - 15:30 Yusuke Kobayashi: Restricted 2-matchings and Discrete Convexity
15:30 - 16:00 Csaba Király: Rigid Graphs and an Augmentation Problem
16:00 - 16:30 Tea and cake
16:30 - 17:00 Alina Ene: The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
17:00 - 17:30 Morteza Zadimoghaddam: Randomized Composable Core-sets for Distributed Submodular and Diversity Maximization

Friday, October 9

9:30 - 10:00 Tony Nixon: Rigidity of Graphs on Expanding Spheres
10:00 - 10:30 Tasuku Soma: Maximizing Monotone Submodular Functions over the Integer Lattice
10:30 - 11:00 Coffee break
11:00 - 11:30 Sahil Singla: Online Matroid Intersection: Beating Half for Random Arrival
11:30 - 12:00 Standa Zivny: The Power of Sherali-Adams Relaxations for General-Valued CSPs
12:00 - 16:00 Lunch break & Discussions
16:00 - 16:30 Tea and cake – End of workshop

Participants

Person
Affiliation
Period of stay
Ahmad Abdi University of Waterloo
Niv Buchbinder Tel Aviv University
Kristóf Bérczi MTA-ELTE Egerváry Research Group
Gruia Calinescu Illinois Institute of Technology
Deeparnab Chakrabarty Microsoft Research
Katie Clinch Queen Mary, University of London
Michelangelo Conforti Università di Padova
William Cook University of Waterloo
Gerard Cornuejols Carnegie Mellon University
Agnes Cseh TU Berlin
Marco Di Summa Università degli Studi di Padova
Alina Ene University of Warwick
Uriel Feige Weizmann Institute
Yuval Filmus Institute for Advanced Study
Elisabeth Finhold UC Davis
András Frank Eotvos University Budapest
Satoru Fujishige Research Institute for Mathematical Sciences
Corinna Gottschalk RWTH Aachen
Hakan Guler Queen Mary, University of London
Stephan Held Universität Bonn
Stefan Hougardy Universität Bonn
Satoru Iwata University of Tokyo
Bill Jackson Queen Mary
Tibor Jordán Eötvös University
Marek Karpinski Universität Bonn
Csaba Király Eötvös University
Tamás Király Eötvös University Budapest
Yusuke Kobayashi University of Tsukuba
Bernhard Korte Universität Bonn
Jochen Könemann University of Waterloo
Oded Lachish Birkbeck, University of London
Yin Tat Lee Massachusetts Institute of Technology
S Thomas McCormick Sauder School of Business, UBC
Matthias Mnich Universität Bonn
Kazuo Murota Tokyo Metropolitan University
Seffi Naor Technion
Alantha Newman CNRS
Tony Nixon Lancaster University
Neil Olver VU University Amsterdam & CWI
Kanstantsin Pashkovich University of Waterloo
Britta Peis RWTH Aachen
Kent Quanrud University of Illinois at Urbana-Champaign
Orit Raz Tel Aviv University
Heiko Röglin Universität Bonn
Bernd Schulze Lancaster University
Roy Schwartz Technion - Israel Institute of Technology
András Sebo CNRS
Akiyoshi Shioura Tokyo Institute of Technology
Aaron Sidford Microsoft Research New England
Sahil Singla Carnegie Mellon University
Tasuku Soma University of Tokyo
Jose Soto Universidad de Chile
Shin-ichi Tanigawa Kyoto University
Fabio Tardella Sapienza University of Rome
Louis Theran Aalto University
Jan Vondrák IBM Almaden Research Center
Jens Vygen Universität Bonn
Justin Ward University of Warwick
Yutaro Yamaguchi University of Tokyo
Yu Yokoi University of Tokyo
Morteza Zadimoghaddam Google Inc.
Rico Zenklusen ETH Zurich
Stanislav Zivny University of Oxford
Anke van Zuylen College of William & Mary
Wird geladen