1 of 12

Sketching Graphs and Combinatorial Approximation

​

Robert Krauthgamer, Weizmann Institute of Science

​

​

Algorithms & Optimization at Google Zurich, Nov. 2017

TexPoint fonts used in EMF.

Read the TexPoint manual before you delete this box.: AAA

2 of 12

Combinatorial Optimization via Sketches

Sketching Graphs and Combinatorial Approximation

2

 

 

optimize

estimator

 

 

 

 

 

3 of 12

 

  •  

Sketching Graphs and Combinatorial Approximation

3

4 of 12

All Graph Cuts (“for all”)

  •  

Sketching Graphs and Combinatorial Approximation

4

5 of 12

Lower Bound

  •  

Sketching Graphs and Combinatorial Approximation

5

6 of 12

All Graph Cuts (“for each”)

  •  

Sketching Graphs and Combinatorial Approximation

6

7 of 12

Example Application: Min-Cut

  •  

Sketching Graphs and Combinatorial Approximation

7

8 of 12

Terminal Cuts

  • Suppose G has k terminals K⊂½V(G) (“important” vertices)

​

​

​

​

​

​

​

​

  • We care about terminal cuts:
    • mincutG(S) = minimum-capacity cut separating S⊂½K from•S=KnS.
    • (Equivalent to the maximum flow between S and•S.)

​

Sketching Graphs and Combinatorial Approximation

8

G:

9 of 12

Vertex Sparsifiers

  •  

Sketching Graphs and Combinatorial Approximation

9

quality

10 of 12

Higher Quality?

  •  

Sketching Graphs and Combinatorial Approximation

10

11 of 12

Main Idea: Structure Sampling

  • Edge sampling useful for edge-sparsifiers [BK’96,SS’11]
  • But does not work here, need to sample entire sub-structures

​

Sketching Graphs and Combinatorial Approximation

11

original graph

sampling edges

sampling paths

12 of 12

Further Questions

High-level plan:

  • Sketching for other combinatorial features (hypergraphs, CSPs)
  • Tradeoff sketch-size and approximation?
  • Compare representations (graphical vs. data structure)
  • Connections between distances/cuts/flows?

Sketching Graphs and Combinatorial Approximation

12

Thank You!

Combinatorial Optimization vs. Information Theory