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
Random Sampling
Random Sampling
A Polling Problem
Analysis: Chernoff Bound
Application to Polling
Analysis
Sampling for Min-Cuts
Min-cut Duality
Example
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
Two Problems
Sampling
Simple First Step
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
Repair Methods
Nonuniform Sampling
s-t Min-Cuts
The Problem
Biased Sampling
Problem Old Time New Time
Strong Components
Nonuniform Sampling
Nonuniform Sampling
Compression Theorem
Application
Proof (approximation)
Strength Lemma
Proof (edge count)
Construction
NI Certificate Algorithm
Approximate Flows
Smoothing
Exact Flow Algorithms
Residual Graphs
First Try
Application
Proof
Analysis
Strong Connectivity
Analysis
Summary
Network Reliability
The Problem
Approximation Algorithms
Monte Carlo Simulation
Chernoff Bound
Application
For network reliability
Rare Events
DNF Counting
Rewrite problem
Satisfaction Matrix
New sample space
Sampling Nonzeros
Few Samples Needed
Reliability Connection
Focus on Small Cuts
Review
Proof of Theorem
Algorithm
Combine
Summary
Conclusions
Conclusion
Randomized Methods
Random Selection
Monte Carlo
Random Sampling
Randomized Rounding
Generalization
Directed Graphs?
Open problems
Randomization in
Graph Optimization Problems