Graduate Algorithms Seminar (CpSc 9500, Section 2)

The Friday Algorithms Seminar meets every Friday from 3:30-4:30 in McAdams Hall room 114. To join the mailing list in order to receive talk announcements, please email the seminar or ganizer, Dr. Brian Dean ( Students may register every semester for 1 unit of credit, for which attendance every week is expected (please contact Brian Dean if you are interested in registering for more than 1 unit of credit).

Next talk

Title: Approximating the Number of Perfect Matchings in a Bipartite Graph
Speaker: Hayato Ushijima-Mwesigwa
Location: McAdams 114
Date/Time: Friday, September 12, 3:30pm-4:30pm

Abstract: Computing the permanent of a 0-1 square matrix is equivalent to counting the number of perfect matchings in a bipartite graph. The permanent is a function similar to the determinant. Despite it's apparent similarity, it is believed that (under standard complex-theoretic assumptions) exact computation is not possible in polynomial-time. In this talk, we present a fully-polynomial randomized approximation scheme which provides an arbitrarily close approximation in time that depends only polynomially on the input size and the desired error. We do this by making a reduction to (almost) uniform sampling of perfect and "near-perfect" matching in the graph. Sampling is them done using the "Markov chain Monte Carlo" approach. The main part of this talk will be defining a Markov Chain and showing that it "mixes rapidly".

For more information on the algorithms seminar and a list of past topics, please see:

Previous Talks

FALL 2014
Date Speaker Topic
9/5/2014 Brian Dean Metric Space Embeddings 101
8/29/2014 Rommel Jalasutram Approximating the Stable Matching Problem with Ties and Incomplete Lists
8/22/2014 Brian Dean New Results for Unsplittable Stable Allocation Problems
Date Speaker Topic
4/25/2014 Christopher Corsi Filesystem Data Structures and their Challenges
4/18/2014 Ben Cousins A Cubic Algorithm for Computing Gaussian Volume
4/11/2014 Brian Dean Perfectly-Balanced Trees
4/4/2014 Paul Kilgo A Secialized Algorithm for Path Generation for the Numerical Computation of Path Integrals
3/28/2014 Yihua Ding A Polynomial-Time Self Stabilizing Algorithm for Minimal Total Dominating Set in an Arbitrary Graph
3/14/2014 Brian Dean Approximate Selection
3/7/2014 Rommel Jalasutram Improving Randomized Resource Allocation
2/28/2014 Brian Dean Succinct Data Structures for Representing Trees
2/21/2014 Brian Dean Thinking Outside the Box -- Algorithms for Klee's Measure Problem
2/14/2014 Brian Dean Algorithms and Finding True Love
2/7/2014 Rommel Jalasutram Coloring 3-Colorable Graphs
1/31/2014 Brian Dean Special Properties of Random Inputs
1/24/2014 Doug Shier A Simple Network Approach to Ranking Athletic Teams
1/17/2014 Brian Dean Offense-Defense Ranking Algorithms
FALL 2013
Date Speaker Topic
12/6/2013 Brian Dean History-Independent Data Structures
11/22/2013 Rommel Jalasutram Randomized Routing
11/15/2013 Hayato Ushijima-Mwesigwa Counting Spanning Trees
11/1/2013 Brian Dean Approximating the Prize-Collecting Traveling Salesman Problem
10/25/2013 Brian Dean Sorting Without Transitivity
10/18/2013 Brian Dean Integer Range Searching
10/11/2013 Brian Dean Fast Minimum Spanning Tree Verification
10/4/2013 Brian Dean Linkages and Graph Rigidity
9/27/2013 Michael Burr Amortization: Classical, Algebraic, and Continuous
9/20/2013 Brian Dean Recent Bounds for Hashing with Linear Probing
9/13/2013 Brian Dean Parametric Shortest Paths and Min Cuts in Planar Graphs
9/6/2013 Brian Dean Sketchy Data Structures
8/30/2013 Ágnes Cseh Stability in Networks
8/23/2013 Brian Dean Wheels within Wheels and Ear Decompositions
Date Speaker Topic
4/26/2013 Sam Casacio Sparse Voxel Octrees
4/19/2013 Brian Dean Scaling Algorithms and Shortest Paths
4/12/2013 Brian Dean Spanning Trees and Approximation
4/5/2013 Brian Dean Maximum Adjacency Orderings in Flows and Cut Algorithms
3/29/2013 Brian Dean Geometric Minimum Spanning Tree Problems
3/8/2013 Rommel Jalasutram Approximating k-Median via Pseudo-Approximation
2/15/2013 Brian Dean Finding the k Minimum Spanning Trees
2/8/2013 Raghuveer Mohan Finding the k Shortest Paths
2/1/2013 Brian Dean Extreme Points in Approximation Algorithms
1/18/2013 Rommel Jalasutram Simple, Fast and Deterministic Gossip and Rumor Spreading
1/11/2013 Brian Dean Path Decompositions of Trees
FALL 2012
Date Speaker Topic
11/30/2012 Brian Dean Locality-Sensitive Hashing and Similarity Computation
11/16/2012 Rommel Jalasutram Probabilistic Approximation of Metrics by Tree Metrics
11/9/2012 Brian Dean Introduction to Personal Pagerank
10/26/2012 Brian Dean On-Line Algorithms and Lost Cows
10/19/2012 Chad Waters Classic Nintendo Games are (NP-)Hard
10/12/2012 Brian Dean Embeddings in Approximation Algorithms
10/5/2012 Brian Dean My Favorite Problems from IOI 2012
9/28/2012 Rommel Jalasutram Randomized Rounding and Approximations
9/14/2012 Brian Dean Approximating the Traveling Salesman Path Problem (continued)
9/7/2012 Brian Dean Approximating the Traveling Salesman Path Problem
8/31/2012 Brian Dean How to Cut a Cake
Date Speaker Topic
4/27/2012 Raghuveer Mohan O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List
4/20/2012 Aditya Sriram Modeling Causality and Making Predictions
4/13/2012 Brian Dean How to Hang a Picture in Polynomial Time
4/6/2012 Rommel Jalasutram Aggregating Inconsistent Information. Ranking and Clustering
3/30/2012 Brian Dean Simple Algorithms for Approximate Order Statistics
3/9/2012 Brian Dean Feature Selection via Linear Programming
3/2/2012 Brian Dean Introduction to Streaming Algorithms
2/24/2012 Brian Dean Sparse Fourier Transforms
2/17/2012 Brian Dean Parametric Search
2/10/2012 Rommel Jalasutram Popular Matchings
2/3/2012 Brian Dean High-Multiplicity Scheduling Problems
1/27/2012 Brian Dean The Benefit of Doing Tasks in Random Order
1/20/2012 Sam Bryfczynski Using Clustering and Visualizations to Analyze Student Work
FALL 2011
Date Speaker Topic
12/02/2011 Sumod Mohan Gomory-Hu Clustering and Application to Image Segmentation
11/18/2011 Rommel Jalasutram Building the Cactus of a Graph
11/11/2011 Brian Dean Estimating Network Reliability
11/4/2011 Brian Dean Maximum Adjacency Orderings and Minimum Cuts
10/21/2011 Brian Dean Realistic 3D Cell Cytoskeletal Reconstruction from Machine Vision Analysis of Confocal Microscopy Images
10/14/2011 Rommel Jalasutram Very Simple Methods for All Pair Network Flow Analysis
10/07/2011 Brian Dean Global Minimum Cuts in Planar Graphs
9/30/2011 Brian Dean Algorithms for Sports
9/23/2011 Brian Dean Clustering with Parametric Minimum Cuts
9/16/2011 Brian Dean On-Line Load Balancing
9/9/2011 Brian Dean Community Structure in Signed Networks
9/2/2011 Brian Dean Computing the Girth of a Graph
8/26/2011 Brian Dean Selected Problems from Recent Informatics Olypiads
Date Speaker Topic
4/29/2011 Elizabeth Matthews Procedural Generation of Story-Driven Maps
4/22/2011 Brian Dean Fully-Dynamic Graph Connectivity
4/15/2011 Aditya Sriram Learning Topologies of Graphical Models using Parallel Interactive Markov Chain Monte Carlo methods
4/8/2011 Ben Cousins Jane: A New Tool for the Cophylogeny Reconstruction Problem
4/1/2011 Brian Dean Maintaining Dynamic Strongly-Connected Components and Transitive Closure in Directed Graphs
3/11/2011 Chad Waters Randomized Reduction
3/4/2011 Gift Kositwattanarerk Modern Algorithms for the Decoding Problem
2/25/2011 Rommel Jalasutram Weighted On-Line Bipartite Matching
2/18/2011 Raghuveer Mohan 2D Van Emde Boas Structures
2/11/2011 Chad Waters Optimal Pattern Matching in LZW-Compressed Strings
2/4/2011 Matt Dabney Approximating the Highway Problem
1/28/2011 Brian Dean Heuristics for Large-Scale Assignment Problems
1/21/2011 Brian Dean Matching a Million Points
1/14/2011 Brian Dean Auction Algorithms for Optimal Matchings
FALL 2010
Date Speaker Topic
12/3/2010 Brian Dean Approximation and Compression in Shortest Path Computation
11/19/2010 Shelby Darnell A Genetic Algorithm for Feature Reduction on Finger Shape and Dorsum Surface Features
11/5/2010 Rommel Jalasutram Multiple-Source Shortest Paths in Planar Graphs
10/29/2010 Raghuveer Mohan A Simpler Implementation and Analysis of Chazelle’s Soft Heaps
10/22/2010 Brian Dean Parabolic Lifting, Etc.
10/15/2010 Brian Dean Encoding Numbers in Binary without Wasting Space
10/1/2010 Brian Dean Double Displacement and Deterministic Perfect Hash Table Construction
9/24/2010 Rommel Jalasutram Better and Simpler Approximation Algorithms for the Stable Matching Problem
9/17/2010 Brad Paynter An Optimization Approach to a Geometric Packing Problem
9/10/2010 Brian Dean Maximum Flows in Planar Graphs II
9/3/2010 Brian Dean Maximum Flows in Planar Graphs I
8/27/2010 Brian Dean Eulerian Augmentation
Date Speaker Topic
4/23/2010 Brian Dean Binary Search
4/16/2010 Brian Dean Algorithms for the Optimal Staying up Late Problem
4/9/2010 Rommel Jalasutram Self-Stabilizing Depth-First Search
4/2/2010 Shelby Darnell Reducing 3D Finger Surface Features Using Computational Intelligence
3/26/2010 Brian Dean Path Packing, Covering, and Cutting in Trees
3/12/2010 Brian Dean Splay Trees, Dynamic Trees, and Tango Trees
3/5/2010 Brian Dean Random Walks, Sampling, and Approximate Counting
2/26/2010 Sumod Mohan Computer Vision and Graph Cuts
2/19/2010 Rommel Jalasutram The Complexity of Computing a Nash Equilibrium
2/12/2010 Brian Dean System-Optimal Versus User-Optimal Network Routing
2/5/2010 Raghuveer Mohan New Algorithms for Building Cartesian Trees
1/29/2010 Brian Dean Optimal Stable Marriage Algorithms
1/22/2010 Brian Dean Adaptive Stable Marriage Algorithms
1/15/2010 Wayne Goddard Master-Slave Self-Stabilizing Algorithms
1/8/2010 Brian Dean Parametric Maximum Flows and Graph Clustering
FALL 2009
Date Speaker Topic
12/4/2009 Brian Dean Algorithmic Games
11/20/2009 Pradip Srimani Recent Results in Self-Stabilizing Algorithms
11/13/2009 Brian Dean Fair and Unfair Flow Allocations
11/6/2009 Brian Dean My Favorite Algorithmic Programming Competition Problems
10/30/2009 Brian Dean Algorithms for Problems on Regular Bipartite Graphs
10/16/2009 Brian Dean A Simple Method for Analyzing Randomized Divide-and-Conquer Algorithms
10/2/2009 David Jacobs A Self-Stabilizing Algorithm for Maximal Matching
9/18/2009 Steve Hedetniemi A New Look at an Old Self-Stabilizing Algorithm for {2}-Domination
9/11/2009 Brian Dean Encoding Connectivity in Graphs
9/4/2009 Brian Dean Reconstructing Edge-Disjoint Paths
8/28/2009 Brian Dean Shortest Path Computation in Planar Graphs
Date Speaker Topic
4/17/2009 Brian Dean Time-Dependent Shortest Path and Network Flow Problems
4/10/2009 Brian Dean Approximating Shortest Path Distances and Diameter
4/3/2009 Brian Dean New Approaches for Learning Greedy Orderings
3/27/2009 Wayne Goddard Self-Stabilizing Algorithms for Domination with a Distributed Daemon
3/13/2009 Brian Dean Shortest Paths and Matrix Multiplication
3/6/2009 Steve Hedetniemi NP-completeness Methods of Alice McRae: A Tutorial on NP-completeness
2/27/2009 Brad Paynter An Optimization Approach to a Geometric Packing Problem
2/20/2009 John Dabney An Efficient Algorithm for Verifying Stable Matchings
2/13/2009 Brian Dean Stable Allocation Problems and Algorithms
2/6/2009 Brian Dean Similarity Computation Based on Connectivity
1/30/2009 Brian Dean Approximating the Bounded-Degree Minimum Spanning Tree Problem
1/23/2009 Brian Dean Minimum-Degree Spanning Trees
1/16/2009 Brian Dean Rank-Sensitive Priority Queues
1/9/2009 Brian Dean Min-Max Theorems in Discrete Optimization
FALL 2008
Date Speaker Topic
12/5/2008 Jeremy Carter Folding and Cutting Paper
11/21/2008 Brian Dean Using Linear Programming to Find Bugs in Computer Programs and Humans
11/14/2008 Brian Dean Semidefinite Programming and Approximation Algorithms
11/7/2008 Brian Dean Finding a Central Element
10/31/2008 Daniela Ferrero Directed Hypergraphs as Interconnection Networks Models
10/24/2008 Brian Dean Lagrangian Relaxation, Parametric Optimization, and Spanning Tree Problems
10/17/2008 David Jacobs Three Ways to Compute the Characteristic Polynomial of a Tree
10/10/2008 Brian Dean Parametric Search and Ratio Objectives
9/26/2008 Pradip Srimani Introduction to Distributed Localized Graph Algorithms
9/19/2008 Brian Dean Unsplittable Bipartite Matchings
9/12/2008 Brian Dean Convex Bipartite Matchings
9/5/2008 Brian Dean On-Line Bipartite Matching
8/29/2008 Brian Dean Popular Matchings