Chandra Chekuri's Talks

Caveat Lector: Talk slides tend to be incomplete both in content and references. Moreover, it is common to sacrifice precision (and also correctness) to help in exposition. If you notice some thing egregious let me know.

Copyright: Material on this web page is Copyright 1999-2011 Chandra Chekuri. You are free to download, print, copy, and/or distribute anything on this page. Nothing on this page may be sold in any form for commerical purposes. If you use the material directly in any substantial way please give proper credit.

Recent Talks

  • Speeding up MWU based Approximation Schemes and Some Applications
    .pptx, .pdf
    Shonan Workshop on Algorithms and Optimization under Uncertainty, May 22-25 , 2017.
  • Routing Symmetric Demands and Directed Treewidth
    .pptx, .pdf
    Southern Italian Workshop on Algorithms and Graphs, September 25-30, 2016.
  • Impact of Network Coding on Combinatorial Optimization
    .pptx, .pdf, video
    DIMACS Workshop on Network Coding: the Next 15 Years, December 15-17, 2015.
  • Element Connectivity Preserving Graph Reduction Step
    .pdf, video
    Connectivity Workshop, Hausdorff Research Institute for Mathematics, Bonn, September 9, 2015.
    See also an associated manuscript on some open problems.
  • Recent developments in the structure of large-treewidth graphs
    Theory Seminar, Harvard CS Department, April 13, 2015.
  • Degree-3 Treewidth Sparsifiers
    .pptx, .pdf.
    Talk at SODA, Jan 4, 2015.
  • Treewidth, Applications and Recent Developments
    .pptx, .pdf, video
    Tutorial at NIPS, Dec 8, 2014.
  • Routing and Treewidth: Recent Developments
    .pptx, .pdf and video of talk available here.
    BIRS workshop on Approximation, Aug 8, 2014.
  • Polynomial Bounds for the Grid-Minor Theorem
    Series of lectures, University of Bergen, May 19-22, 2014.
    Slides coming soon. Most slides borrowed from Julia Chuzhoy's series.
  • Structure of Large-Treewidth Graphs: Recent Developments
    Discrete Mathematics and Optimization Seminar, McGill University, March 17, 2014.
  • Approximation Algorithms for Euler Genus and Related Problems
    Theory seminar in CS, and seminar in Math dept at UIUC, Feb 3, 2014.
  • Multiroute Flows and Node-weighted Network Design
    .pptx and .pdf (large file) and .pdf (smaller file) and video of talk can be found here.
    Workshop on Flexible Network Design, Fields Institute (Toronto), July 2013.
  • Large-Treewidth Graph Decompositions and Applications
  • Multicommodity Flows and Cuts in Polymatroidal Networks
  • Algorithms for submodular objectives: continuous extensions and dependent randomized rounding
    .pptx and .pdf (large file)
    Colloquium, TTI Chicago, December 7, 2011.
  • Buy at Bulk Network Design (with Protection)
    .pptx and .pdf (large file)
    Workshop on Approximation Algorithms: The Last Decade and the Next, Princeton, June 2011.
  • Submodular set function maximization via the multilinear relaxation and dependent randomized rounding
    .pptx and .pdf (large file)
    Plenary talk, CanaDAM, Victoria, May-June, 2011.
  • Dependent Randomized Rounding for Matroids and Applications
    .pptx and .pdf (large file)
    Invited talk, Midwest Theory Day, Chicago, December 11, 2010.
  • Submodular set function maximization: A mini survey
    .pptx and .pdf (large file)
    Invited talk, Bellairs Workshop on Approximation Algorithms, Barbados, March, 2010.
  • Online Broadcast Scheduling: New Perspectives and Results
    .pptx and .pdf (large file)
    Invited talk, MAPSP, Abbey Rolduc, June-July 2009.
  • Orienteering and related problems: mini-survey and open problems
    .pptx and .pdf
    Workshop on Approximation Algorithms and their Limitations, TTI Chicago, February 2009.
  • New algorithms for Disjoint Paths and Routing Problems
    .ppt and .pdf
    Colloquium, Dept. of Computer Science, Simon Fraser University, April 28, 2008.
  • Algorithmic Challenges in Optical Network Design
    (joint with Lisa Zhang) .pdf
    DIMACS Tutorial on Algorithms for Next Generation Networks, August 6 - 8, 2007.
  • Older Talks

  • Multiple Knapsack and Generalized Assignment
    Lucent Bell Labs, 2001??

  • Back to Chandra's home page.