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 sometimes also correctness) to help in exposition. Please write and ask if you notice some thing egregious or need clarification.

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

  • Allocations with Submodular Valuations via Continuous Relaxations
    GAME-ARTS, IISc Bengaluru, July 19, 2024.

  • Densest Subgraph: A case study on the interplay between algorithms, structure, and optimization
    .pdf
    IISc Bengaluru, July 12, 2024.

  • On Polyhedral Formulations for (Subset) Feedback Vertex Set

  • Approximation Algorithms for Network Design in Non-Uniform Fault Models
    video
    Theory Seminar, IISc Bengaluru, Nov 3, 2023.

  • Independent Sets in Elimination Graphs: Submodular Objective
    .pdf
    Short talk at APPROX 2023 given by Karthik Chandrasekharan on behalf of authors.

  • Approximation Algorithms for Network Design in Non-Uniform Fault Models
    .pdf
    Theory Seminar, EPFL Laussane, July 21, 2023.

  • Densest Subgraph: Supermodularity, Iterative Peeling and Flow

  • Covering Multiple Submodular Constraints, Special Cases and Applications
    .pdf
    CANADAM 2021. May 25, 2021 (online talk).

  • k-Cut in Graphs and Hypergraphs
    .pptx
    Dartmouth Theory Seminar. Oct 30, 2020 (online talk).

  • k-Cut in Graphs and Hypergraphs
    AAIM 2020, Zhejiang, China. Aug 11, 2020 (online talk due to Covid-19).

  • Parallel Algorithms for Submodular Function Maximization
    .pptx, .pdf
    RIMS, Kyoto, Jan 13, 2020

  • Interplay of discrete and continous optimization: a case study via submodular function maximization
    .pptx
    Univ of Iowa, Oct 30, 2019

  • Submodular Function Maximization via MWU
    .pptx
    11th Israel CS Theory Day, The Open University, Tel Aviv, Dec 11, 2018

  • Approximating the Held-Karp bound for Metric-TSP in Near-Linear Time
    .pptx, .pdf
    Highlights of Algorithms (HALG) 2018.

  • On Approximating Covering Integer Programs
    .pptx
    Workshop on Flexible Network Design, Univ of Maryland, May 22-25 2018

  • Tree packing, Mincut and Metric-TSP
    .pptx
    Seminar at TTI Chicago, May 3, 2018.

  • Speeding up MWU based Approximation Schemes and Some Applications
    .pptx, .pdf
    Theory seminar at UT Austin, Feb 9, 2018.

  • A Note on Survivable Network Design
    .pptx, .pdf
    Symposium on Simplicity in Algorithms (SOSA), January 2018.

  • Multipath Routing to Minimize Congestion via Multiroute Flows
    .pptx, .pdf
    Symposium on Simplicity in Algorithms (SOSA), January 2018.

  • 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
    .pdf
    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
    .pdf
    Discrete Mathematics and Optimization Seminar, McGill University, March 17, 2014.

  • Approximation Algorithms for Euler Genus and Related Problems
    .pdf
    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.

  • Maximizing A Submodular Set Function (Revisited)
    .pdf
    CRM Workshop on Approximation Algorithms, Montreal, June 12 - 14, 2006.

    • Older Talks

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

    • Back to Chandra's home page.