October 5-9, 2015
HIM Lecture Hall, Poppelsdorfer Allee 45
Organizers:
Satoru Iwata, Tibor Jordán, Jan Vondrák
Topics: Rigidity, Submodularity, Discrete Convexity
© HIM
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 |
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 |