Completed
Zeev Nutov: On LP-relaxations for the tree augmentation problem
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Combinatorial Optimization - Trimester Program Lectures
Automatically move to the next video in the Classroom when playback concludes
- 1 Kazuo Murota: Discrete Convex Analysis (Part 1)
- 2 James Lee: Semi Definite Extended Formulations and Sums of Squares (Part 1)
- 3 Matthias Mnich: Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments
- 4 Jonas Witt: Dantzig Wolfe Reformulations for the Stable Set Problem
- 5 Yin Tat Lee & Aaron Sidford: Faster Cutting Plane Methods and Improved Running Times for Submodular
- 6 Victor Chepoi: Simple connectivity, local to global, and matroids
- 7 Heiko Röglin: Smoothed Analysis of Algorithms (Part 1)
- 8 Kazuo Murota: Discrete Convex Analysis (Part 2)
- 9 Tasuku Soma: Maximizing Monotone Submodular Functions over the Integer Lattice
- 10 Kent Quanrud: Streaming Algorithms for Submodular Function Maximization
- 11 Vivek Madan: Simple and fast rounding algorithms for directed and node weighted multiway cut
- 12 Matthias Poloczek: New Approximation Algorithms for MAX SAT Simple, Fast, and Excellent in Practice
- 13 Chandra Chekuri: On element connectivity preserving graph simplification
- 14 Anupam Gupta: The Independent Set problem on Degree d Graphs
- 15 Sahil Singla: Online Matroid Intersection Beating Half for Random Arrival
- 16 Linda Farczadi: The nucleolus of matching games
- 17 Rico Zenklusen: An O(1)-approximation for minimum spanning tree interdiction
- 18 Jens Vygen: Reassembling trees for the traveling salesman
- 19 Kazuo Murota: Extensions and Ramifications of Discrete Convexity Concepts
- 20 Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm
- 21 Aravind Srinivasan: Approximating integer programming problems by partial resampling
- 22 Kazuo Murota: Discrete Convex Analysis (Part 3)
- 23 Agnes Cseh: Popular matchings
- 24 Laurence Wolsey: A polyhedral approach to the maximum convex subset problem in 2-d
- 25 Robert Weismantel: Affine TU decomposition of matrices
- 26 András Frank: Non TDI Optimization with Supermodular Functions
- 27 Monique Laurent: Convergence analysis of hierarchies for polynomial optimization
- 28 Ahmad Abdi: Packing odd T-joins with at most two terminals
- 29 Zoltán Szigeti: Connectivity Problems (Part 1)
- 30 Chaitanya Swamy: Signaling in Bayesian Games
- 31 Wolfgang Mader: Critical vertices in k connected digraphs
- 32 Yuval Filmus: Monotone Submodular Optimization over a Matroid
- 33 Rico Zenklusen: The Submodular Secretary Problem Goes Linear
- 34 Rahul Savani: Polymatrix Games Algorithms and Applications
- 35 Standa Zivny: The Power of Sherali Adams Relaxations for General Valued CSPs
- 36 Volker Kaibel: A simple geometric proof showing that almost all 01 polytopes have exponential ...
- 37 Anja Fischer: Polynomial Matroid Optimisation Problems
- 38 Zeev Nutov: On LP-relaxations for the tree augmentation problem
- 39 Alexander Schrijver: The partially disjoint paths problem
- 40 Seffi Naor: Recent Results on Maximizing Submodular Functions
- 41 Andreas E. Feldmann: A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs
- 42 Alina Ene: The Power of Randomization Distributed Submodular Maximization on Massive Datasets
- 43 Shin-ichi Tanigawa: Sufficient Conditions for Unique Graph Realizations
- 44 András Sebő: Travelling salesmen on bounded degree trails
- 45 Dominik Peters: Structural Tractability in Hedonic Games
- 46 Ruta Mehta: A Market for Scheduling, with Applications to Cloud Computing
- 47 Vahab Mirrokni: Coordination Mechanisms and Price of Anarchy via Fenchel Duality
- 48 Kousha Etessami: The complexity of computing a quasi perfect equilibrium for n player extensive form
- 49 Edith Elkind: Coalitional Games on Sparse Social Networks
- 50 Marco Di Summa: Cut generating functions
- 51 Chidambaram Annamalai: Finding Perfect Matchings in Bipartite Hypergraphs
- 52 Monaldo Mastrolilli: On some easy problems that are hard for the Lasserre hierarchy
- 53 Jon Lee: Comparing polyhedral relaxations via volume
- 54 Christos Kalaitzis: Approximating the Maximum Budgeted Allocation Problem using the Configuration LP
- 55 Rachel Cummings: The Strange Case of Privacy in Equilibrium Models
- 56 Akiyoshi Shioura: Analysis of L-convex Function Minimization Algorithms and App. to Auction Th.
- 57 Gyula Pap: Linear matroid matching in the oracle model
- 58 Jørgen Bang-Jensen: Antistrong digraphs
- 59 Viswanath Nagarajan: Approximation Friendly Discrepancy Rounding
- 60 M. Zadimoghaddam: Randomized Composable Core-sets for Submodular Maximization
- 61 Niv Buchbinder: Deterministic Algorithms for Submodular Maximization Problems
- 62 Parinya Chalermsook: Graph products, hardness of approximation, and beyond
- 63 Yun Kuen (Marco) Cheung: Asynchronous Tatonnement and Coordinate Descent
- 64 Satoru Fujishige: Combinatorial Polynomial Algorithms for Skew bisubmodular Function Minimization
- 65 Tamás Király: Blocking optimal k arborescences
- 66 Tom McCormick: Discrete Convexity in Supply Chain Models
- 67 Ramamoorthi Ravi: Designing Overlapping Networks for Publish Subscribe Systems
- 68 Zoltán Szigeti: On (2k,k)-connected graphs
- 69 Tony Nixon: Rigidity of Graphs on Expanding Spheres
- 70 Louis Theran: Rigidity of Random Graphs in Higher Dimensions
- 71 Heiko Röglin: Smoothed Analysis of Algorithms (Part 2)
- 72 Jugal Garg: ETR Completeness for Decision Versions of Multi Player Symmetric Nash Equilibria
- 73 Agnes Cseh: Paths to stable allocations
- 74 Yusuke Kobayashi: Restricted 2 matchings and Discrete Convexity
- 75 Heiko Röglin: Smoothed Analysis of Algorithms (Part 3)
- 76 James Lee: Semi Definite Extended Formulations and Sums of Squares (Part 3)
- 77 Csaba Király: Rigid Graphs and an Augmentation Problem
- 78 James Lee: Semi Definite Extended Formulations and Sums of Squares (Part 2)
- 79 Zoltán Szigeti: Connectivity Problems (Part 3)
- 80 Bill Jackson: Generic Rigidity of Point Line Frameworks
- 81 Bernd Schulze: Characterizing Minimally Flat Symmetric Hypergraphs
- 82 Zoltán Szigeti: Connectivity Problems (Part 2)
- 83 Troels Bjerre Lund: Timeabillity of Extensive-Form Games
- 84 Tamás Király: Complexity of finding equilibria in linear service providing games
