<big><big>
<big><big>CWI-DIAMANT Seminar Combinatorics and Optimization </big> </big>
The seminar is organized by the research group PNA1: Algorithms, Combinatorics and Optimization on a bi-weekly basis and takes place at CWI (see here for directions).
For information you may contact Monique Laurent (monique at cwi.nl) or Guido Schaefer (g.schaefer at cwi.nl).
See here for details about the Working group on Algebra and Combinatorics.
Event: CWI seminar day
Title: Smoothed Analysis Day
Lectures by B. Vöcking, H. Röglin, B. Manthey, T. Vredeveld, and G. Schäfer
Date/Location: Friday Februrary 26, 9h30 to 17h00, room L120 (to be confirmed), CWI-Amsterdam
Speaker: Simi Haber, Tel Aviv University
Title: Zero-one laws for random regular graphs
Date/Location: Thursday January 7, 11h00, L015, CWI-Amsterdam Speaker: Sylvia Boyd, University of Ottawa
Title: On the integrality gap of the multi-survivable network design problem
Date/Location: Wednesday January 6, 10h30, L120, CWI-Amsterdam
2009 Speaker: Dries Vermeulen (University Maastricht)
Title: Non-cooperative solutions for claims problems
Date/Location: Thursday December 17, 16h00, L015, CWI-Amsterdam Speaker: Nicole Immorlica (Northwestern University)
Title: The cooperative game theory foundations of network bargaining games
Date/Location: Wednesday December 9, 10h30, L121, CWI-Amsterdam Event: CWI seminar day
Title: Applications of semidefinite programming
Lectures by C. Bachoc, J. Briet, D. Gijswijt, A. Schurmann, and R. Sotirov.
Date/Location: Thursday December 3, 10h30 to 17h00, Euler zaal, CWI-Amsterdam Event: PhD defense of Fernando de Oliveira Filho
Title: New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization
Date/Location: Tuesday December 1, 10h00, Agnietenkapel (Oudezijds Voorburgwal 231), University of Amsterdam. Speaker: Matthias Mnich (TUE)
Title: Probabilistic Tools for Combinatorial Bounds in Graph Subset, Constraint Satisfaction and Permutation Problems
Date/Location: Wednesday November 4, 10h30, CO.01 (Porta-cabins), CWI-Amsterdam Speaker: Orestis Telelis (CWI)
Title: Facility Location Games with Fair Cost Allocation
Date/Location: Wednesday October 28, 10h30, room L302 (new part of CWI building!), CWI-Amsterdam Speaker: Hans Mittelman (Arizona State University)
Title: Improved bounds for general quadratic assignment problems via semidefinite relaxations
Date/Location: Monday October 5, 10h30, room H22O (Nikhef building), CWI-Amsterdam Speaker: Roland Grappe (INPG, Grenoble)
Title: Partition constrained covering of a symmetric crossing supermodular function
Date/Location: Friday 18 September, 13h00, room H220 (Nikhef building), CWI-Amsterdam Event: PhD defense of Andreas Witzel
Title: Knowledge and Games: Theory and Implementation
Date/Location: Thursday 3 September, 12h00, Agnietenkapel (Oudezijds Voorburgwal 231), University of Amsterdam. Speaker: Janina Brenner (TU Berlin)
Title: Online Cooperative Cost Sharing
Date/Location: Thursday 6 August, 13h30, CO.01, CWI-Amsterdam Event: PhD defense of Erik Jan van Leeuwen
Title: Optimization and approximation on systems of geometric objects
Date/Location: Tuesday 16 June, 10h00, Agnietenkapel (Oudezijds Voorburgwal 231), University of Amsterdam. Speaker: Mahyar Salek (University Southern California & CWI intern)
Title: Auctions for hiring a team, What can or cannot be done
Date/Location: Thursday June 11, 13h30, M280, CWI-Amsterdam Speaker: Frank Sottile (Texas AM University)
Title: Semidefinite representations for orbitopes
Date/Location: Friday June 5, 13h30, M279, CWI-Amsterdam Speaker: Herve Moulin (Rice University, Texas)
Title: Pricing Traffic in a Spanning Network
Date/Location: Thursday May 14, 14h30, room M279, CWI-Amsterdam Speaker: Marijn Heule (TU Delft)
Title: Improving the odds: New lower bounds for Van der Waerden numbers
Date/Location: Thursday May 14, 11h00, room M280, CWI-Amsterdam Speaker: Bart de Keijzer (TU Delft)
Title: Research overview: complexity of fair division problems; design of voting games
Date/Location: Monday May 11, 13h30, room N328 (Nikhef building), CWI-Amsterdam Speaker: Dominik Wojtczak (CWI)
Title: The Complexity cf Nash equilibria in simple stochastic multiplayer games
Date/Location: Thursday April 16, 10h30, room M279, CWI-Amsterdam Speaker: Gunnar Klau (CWI)
Title: Three combinatorial optimization problems in the life sciences
Date/Location: Thursday March 26, 10h30, room M280, CWI-Amsterdam Speaker: Leonid Gurvits (Los Alamos National Laboratory)
Title: Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all
Date/Location: Monday March 23, 14h00, room M279, CWI-Amsterdam Speaker: Antonios Varvitsiotis (Univ. Athens)
Title: Counting the number of embeddings of minimally rigid graphs
Date/Location: Thursday March 19, 10h30, room M279, CWI-Amsterdam Event: DIAMANT seminar day
Title: Applications of semidefinite programming
Lectures by C. Bachoc, H. Cohn, C. Helmberg, E. de Klerk, and R. Thomas.
Date/Location: Friday March 13, Euler zaal, CWI-Amsterdam
Additional lectures by J. Briet and E. Tsigaridas on Wednesday March 11
and by J. Gouveia and B. Meyer on Thursday March 12, all in room M280. Speaker: Guido Schaefer (CWI)
Title: A PTAS for budgeted matching
Date/Location: Thursday February 19, 10h30, room M279, CWI-Amsterdam Speaker: Jarek Byrka (TUE)
Title: Dependant rounding and fault tolerant facility location
Date/Location: Friday January 30, 13h00, room M279, CWI-Amsterdam Speaker: Guido Schaefer (CWI)
Title: Computing optimal network tolls: Work in progress and open problems
Date/Location: Friday January 23, 14h00, room M279, CWI-Amsterdam Speaker: Satoru Iwata (Kyoto Univ.)
Title: The Submodular Vertex Cover Problem
Date/Location: Friday January 9, 13h00, room M279, CWI-Amsterdam 2008 Speaker: Nicole Immorlica (Northwestern Univ.)
Title: Approximating Matches Made in Heaven
Date/Location: Thursday December 18, 14h00, room M280, CWI-Amsterdam Speaker: Janina Brenner (TU Berlin)
Title: Cooperative cost sharing via singleton mechanisms
Date/Location: Thursday December 11, 13h00, room M280, CWI-Amsterdam Speaker: Florian Horn (CWI)
Title: The complexity of Muller games
Date/Location: Friday November 28, 13h00, room M279, CWI-Amsterdam Event: PhD defense of Jarek Byrka
Title: Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria
Date/Location: Monday October 13, 16h00, TU Eindhoven.
as part of the Diamant Algorithms Day. speaker: Philipp Rostalski (ETH, Zurich)
Title: Quasi-Hankel matrices and the real radical ideal
Date/Location: Thursday September 25, 13h00, room M280, CWI-Amsterdam. speaker: Maurits de Graaf (Thales)
Title: The network lifetime problem in ad-hoc networks: results and problems
Date/Location: Friday September 12, 13h00, room M279, CWI-Amsterdam. speaker: Renato Gomes, CWI intern and Northwestern graduate student
Title: Externalities in Keyword Auctions: an Empirical Assessment and a Model of Scoring Rules
Date/Location: Thursday September 4, 15h00, room M280, CWI-Amsterdam. speaker: Achill Schuermann (Univ. Magdeburg)
Title: Computational Geometry of Positive Definite Quadratic Forms
Date/Location: Thursday September 4, 13h00, room M280, CWI-Amsterdam. speaker: Jason Hartline (Northwestern University)
Title: Optimal Mechanism Design - from the 2007 Nobel Prize in Economics to the Foundations of Internet Algorithms
Date/Location: Thursday August 28, 13h00, room M280, CWI-Amsterdam. speaker: Elena Grigorescu, MIT and CWI Intern
Title: 2-transitivity is insufficient for local testability
Date/Location: Thursday August 14, 13h00, room M279, CWI-Amsterdam. speaker: Mohammad Mahdian, Yahoo! Research
Title: Externalities in Online Advertising
Date/Location: Thursday July 24, 13h00, room M279, CWI-Amsterdam. speaker: Aravind Srinivasan (Univ. Maryland)
Title: Dependent rounding and its applications to approximation algorithms
Date/Location: Thursday July 3, 10h00, room M279, CWI-Amsterdam. speaker: Fernando de Oliveira Filho (CWI)
Title: Fourier analysis, linear programming, and densities of distance avoiding sets in R^n
Date/Location: Friday June 6, 13h00, room M280, CWI-Amsterdam. speaker: Seffi Naor (Technion)
Title: A Primal-Dual Approach to Online Optimization Problems
Date/Location: Thursday 15 May, 13h00, room M280, CWI-Amsterdam. speaker: Guido Schaeffer (Technical University Berlin)
Title: Cost Sharing Mechanisms for Combinatorial Optimization Problems
Date/Location: Wednesday 23 April, 13h00, CWI-Amsterdam, M279. speaker: Martin Gairing (International Computer Science Institute, Berkeley)
Title: Selfish Routing in Networks
Date/Location: Monday 21 April, 10h00, CWI-Amsterdam, M279. Celebrating Lex' birthday
13h30: Cor Hurkens, Franklin Magic Squares
14h30: Hein van der Holst, On $\mu(G)$ and other Colin de Verdiere-type parameters
16h15: Rudi Pendavingh, Lifting of matroid representations over partial fields
Date/Location: Friday 18 April, 13h15, CWI-Amsterdam, M280. speaker: Xinhui Wang (Univ. Twente)
Title: Exact algorithms for the Steiner tree problem
Date/Location: Wednesday 16 April, 10h30, CWI-Amsterdam, M279. speaker: Vahab Mirrokni (Microsoft Research, Redmond)
Title: Submodular optimization and online advertisement
Date/Location: Monday 14 April, 10h00, CWI-Amsterdam, M279. Event: PhD defense of Nebojsa Gvozdenovic
Title: Approximating the stability number and the chromatic number of a graph via semidefinite programming
Date/Location: Thursday 10 April, 12h00, Agnietenkapel, University of Amsterdam. speaker: Benny Mounits (CWI)
Title: Upper Bounds for Codes Over Finite Rings via Semidefinite Programming
Date/Location: Thursday 3 April, 13h00, CWI-Amsterdam, M280. speaker: Monique Laurent (CWI)
Title: Comparing some linear algebra methods for (real) solving polynomial equations
Date/Location: Friday February 22, 10h00, CWI-Amsterdam, M280. speaker: Fernando Oliveira de Filho (CWI)
Title: How to destroy all group Steiner trees in a graph?
Date/Location: Friday February 15, 10h00, CWI-Amsterdam, M280. speaker: Anupam Gupta (CMU)
Title: Oblivious Network Design
Date/Location: Monday January 14, 10h30, CWI-Amsterdam, M280. 2007 speaker: Piotr Indyk (MIT)
Title: Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Date/Location: Tuesday December 18, 10h30, CWI-Amsterdam, M279. speaker: Dion Gijswijt (UvA)
Title: Fractional matroid matchings: finding a maximum weight fractional matching
Date/Location: Friday December 7, 13h00, CWI-Amsterdam, M279. speaker: Tobias Mueller (Eurandom)
Title: Circular choosability
Date/Location: Friday November 23, 13h00, CWI-Amsterdam, M279. speaker: Kamal Jain (Microsoft Research)
Title: Atomic Economics
Date/Location: Friday November 16, 13h00, CWI-Amsterdam, M280. speaker: Edith Elkind (University of Southampton)
Title: Frugality in set system auctions: an overview
Date/Location: Monday November 12, 11h00, CWI-Amsterdam, M280. speaker: Lars Schewe (CWI)
Title: Realizability of oriented matroids
Date/Location: Friday November 2, 13h00, CWI-Amsterdam, M280. speaker: Nicole Immorlica (CWI)
Title: Revenue maximization in digital goods auctions
Date/Location: Friday October 12, 13h00, CWI-Amsterdam, M280. speaker: Frank McSherry (Microsoft Research)
Title: Mechanism Design via Differential Privacy
Date/Location: Monday October 1st, 16h00, CWI-Amsterdam, M279. speaker: Jarek Byrka and Steven Kelk
Title: Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
Date/Location: Monday October 1st, 10h00, CWI-Amsterdam, M279. speaker: Erik Jan van Leeuwen
Title: Domination in Geometric Intersection Graphs
Date/Location: Friday September 7, 10h00, CWI-Amsterdam, M280. speaker: Gyula Pap
Title: Packing A-paths subject to node-capacities
Date/Location: Friday August 24, 13h00, CWI-Amsterdam, M279. speaker: Gyula Karolyi
Title: The Combinatorial Nullstellensatz and the Polynomial Method
Date/Location: Friday August 24, 10h00, CWI-Amsterdam, M279. speaker: Amin Saberi
Title: Approximation Algorithms for Fair Allocation of Indivisible Goods
Date/Location: Tuesday July 3, 10h00, CWI-Amsterdam, M280. speaker: Vangelis Markakis
Title: Algorithms for Approximate Nash Equilibria
Date/Location: Friday June 22, 13h00, CWI-Amsterdam, M280. speaker: Benny Mounits
Title: Lower bounds on the minimum average distance of binary codes
Date/Location: Thursday June 7, 10h00, CWI-Amsterdam, H320 (Nikhef). speaker: Arantza Estevez-Fernandez
Title: Sequencing games: an introduction to OR games
Date/Location: Friday May 25, 13h00, CWI-Amsterdam, M280 speaker: Nicole Immorlica
Title: Secretary Problems and Online Auction Design
Date/Location: Tuesday May 15, 13h30, CWI-Amsterdam, M279 speaker: Serguei Norin
Title: Pfaffian orientations of graphs
Date/Location: Tuesday April 17, 10h00, CWI-Amsterdam, M279 speaker: Markus Schweighofer
Title: Sums of hermitian squares of polynomials, the BMV conjecture and Connes' embedding problem
Date/Location: Tuesday April 17, 13h00, CWI-Amsterdam, M279 speaker: Hein van der Holst
Title: Minimum rank of graphs and 2-separations
Date/Location: Tuesday April 17, 15h30, CWI-Amsterdam, M279 speaker: Frank Vallentin
Title: Packing problems in compact metric spaces
Date/Location: Wednesday April 11, 15h00, CWI-Amsterdam, M279 speaker: Frank Vallentin
Title: Voronoi cells of lattices, regular matroids, and a bit of complexity theory
Date/Location: Tuesday March 6, 13h00, CWI-Amsterdam, M280 speaker: Dion Gijswijt
Title: Fractional matroid matching (follow-up)
Date/Location: Thursday Februari 22, 10h00, CWI-Amsterdam, Room M280 speaker: Dion Gijswijt
Title: Fractional matroid matching
Date/Location: Thursday Februari 15, 10h00, CWI-Amsterdam, Room M280 speaker: Katharina Huber (School of Computing Sciences, University of East Anglia)
Title: Median graphs and beyond
Date/Location: Monday January 29, 15h00-17h00, CWI-Amsterdam, Room M280 speaker: Fernando de Oliveira Filho (CWI)
Title: A conjecture of Lovasz concerning bi-critical graphs
Date/Location: Friday January 26, 10h00, CWI-Amsterdam, Room M279 2006 speaker: Steven Kelk (CWI)
Title: Beaches of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems
Date/Location: 08-12-2006, 13h00, CWI-Amsterdam, Room M280 speaker: Lex Schrijver (CWI)
Title: Shortest disjoint paths in planar graphs
Date/Location: 24-11-2006, 13h00, CWI-Amsterdam, Room M280 DIAMANT Intercity Event: Lattice Day
Date: Friday November 10, 2006
Place: University of Leiden. See here for details. speaker: Jarek Byrka (CWI)
Title: A 1.5-approximation algorithm for the metric uncapacitated facility location problem
Date/Location: 20-10-2006, 13h00, CWI-Amsterdam, Room M280
speaker: Erik Jan van Leeuwen (CWI)
Title: Algorithmic aspects of graph minor theory
Date/Location: 06-10-2006, 13h00, CWI-Amsterdam, Room M280
speaker: Hartwig Bosse (CWI)
Title: Symmetries and sums of squares of polynomials
Date/Location: 15-09-2006, 13h00, CWI-Amsterdam, Room M280
DIAMANT/Spinoza Intercity Seminar on Algebra and Symmetries in Combinatorics and Optimization
Date: Friday June 30, 2006.
Location: University of Amsterdam
See here for the list of talks. speaker: Vangelis Markakis (University of Toronto)
Title: Computational Aspects of Game Theory and Microeconomics
Date/Location: 28-06-2006, 10h00, CWI-Amsterdam, Room M280
speaker: Jules van Kempen (Utrecht University)
Title: Online capacity planning of repairs at Rüttchen car dealers
Date/Location: 23-06-2006, 13h00, CWI-Amsterdam, Room M279
speaker: Mike Steel, Director for Biomathematics Research Centre, University of Canterbury (New Zealand)
Title: Combinatorial approaches in phylogenetics
Date/Location: Wednesday 14-06-2006, 10h15, CWI-Amsterdam, Room N328 (NIKHEF building)
speaker: Beniamin Mounits (CWI)
Title: Joint weight enumerators and semidefinite programminng bound for binary codes
Date/Location: 09-06-2006, 13h00, CWI-Amsterdam, Room M279
speaker: Frank Vallentin (CWI)
Title: Semidefinite programming bounds for spherical codes
Date/Location: 15-05-2006, 13h00, CWI-Amsterdam, Room M279
speaker: Stefan van Zwam (TUE)
Title: A semidefinite programming relaxation of the space of Korkin--Zolotarev reduced lattice bases
Date/Location: 28-4-2006, 10h30, CWI-Amsterdam, Room M280
speaker: Monique Laurent (CWI)
Title: Solving systems of polynomial equations via linear algebra
Date/Location: 07-04-2006, 13h00, CWI-Amsterdam, Room M280
speakers: Steven Kelk (CWI) and Leen Stougie (CWI/TUE)
Title: Prefix reversals on strings over finite alphabets
Date/Location: 24-03-2006, 13h00, CWI-Amsterdam, Room M280
speaker: Lex Schrijver, CWI
Title: Tensor algebras and invariant theory
Date/Location: 10-03-2006, 13h00, CWI-Amsterdam, Room M280
Speaker: Vangelis Markakis, University of Toronto, Toronto
Title: Inapproximability Results for Maximizing the Social Welfare in Combinatorial Auctions
Date/Location: Tuesday 14-02-2006, 11h00, CWI-Amsterdam, Room M280
Speaker: Thomas Erlebach, University of Leicester, Leicester
Title: Minimum weight dominating sets in unit disk graphs
Date/Location: Thursday 02-02-2006, 13h00, CWI-Amsterdam, Room M280
DIAMANT Intercity Event: Integer Programming Day
Date: Friday January 27, 2006
Place: Technical University Eindhoven. See here for details. Speaker: Fernando de Oliveira Filho, CWI
Title: Fast matrix multiplication (II)
Date/Location: 20-01-2006, 11h00, CWI-Amsterdam, Room M280
2005 Speaker: Fernando de Oliveira Filho, CWI
Title: Fast matrix multiplication (I)
Date/Location: 16-12-2005, 13h00, CWI-Amsterdam, Room M279
Speaker: Benny Mounits, Technion, Haifa
Title: Upper bounds on sizes of codes via association schemes and linear programming
Date/Location: 02-12-2005, 10h00, CWI-Amsterdam, Room M279
No seminar on 18-11-2005
DIAMANT/EIDMA symposium 2005, Mierlo, November 16-18, 2005. Speaker: Erik Jan van Leeuwen, CWI
Title: Better approximation schemes on disk graphs
Date/Location: 04-11-2005, 13h00, CWI-Amsterdam, Room M279
Speaker: Frank Vallentin, CWI
Title: Computing the minimum distortion for embedding distance-transitive graphs in the Euclidean space
Date/Location: 21-10-2005, 13h00, CWI-Amsterdam, Room H220 (NIKHEF building)
Speaker: Nebojsa Gvozdenovic, CWI
Title: Approximating the chromatic number of a graph by semidefinite programming
Date/Location: 07-10-2005, 13h00, CWI-Amsterdam, Room M279
