Randomization in
Graph Optimization Problems
Randomized Algorithms
Methods
Cuts in Graphs
Optimization with Cuts
Presentation Assumption
Basic Probability
Random Selection
for
Minimum Cuts
Minimum Cut
Max-flow/Min-cut
Flow Algorithms
Contraction
Contraction Algorithm
Slide 14
Picking an Edge
Randomize
Analysis I
Analysis II
Analysis III
Repetition
How fast?
An improvement [KS]
Recursive Algorithm
Main Theorem
Proof Outline
Failure Modes
How do we verify
a minimum cut?
Enumerating Cuts
Cut Counting
Enumeration
Generalization
Summary
Network Reliability
The Problem
Approximation Algorithms
Monte Carlo Simulation
Chernoff Bound
Application
Review
Network reliability problem
Rare Events
DNF Counting
Rewrite problem
New sample space
Sampling Nonzeros
Few Samples Needed
Reliability Connection
Focus on Small Cuts
Proof of Theorem
Algorithm
Combine
Summary
Random Sampling
Random Sampling
Min-cut Duality
Example
Sampling for Approximation
Random Sampling
Sampling Theorem
A Simple Application
Proof of Sampling: Idea
Proof of Sampling
Las Vegas Algorithms
Approximate Tree Packing
Las Vegas Algorithm
Exact Algorithm
Nearly Linear Time
Analyze Trees
Constraint trees
Finding the Cut
Sampling
Simplify
Analyzing a tree
The Dynamic Program
Algorithm: 1-Crossing Trees
2-Crossing Trees
Linear Time
How do we verify
a minimum cut?
Network Design
Problem Statement
Integer Linear Program
Randomized Rounding
k-connected subgraph
Nonuniform Sampling
s-t Min-Cuts
The Problem
Biased Sampling
Problem Old
Time New Time
Strong Components
Nonuniform Sampling
Nonuniform Sampling
Compression Theorem
Proof (approximation)
Strength Lemma
Proof (edge count)
Construction
Certificate Algorithm
Flows
Smoothing
Cleanup
Proof By Picture
Compress Dense Regions
Solve Sparse Flow
Replace Dense
Parts
(keep flow in sparse bits)
“Fill In” Dense Parts
Conclusions
Conclusion
Randomized Methods
Random Selection
Monte Carlo
Random Sampling
Randomized Rounding
Generalization
Directed Graphs?
Open problems
Randomization in
Graph Optimization Problems