A polytope perspective

This section is there to support the paper Online Stochastic Matching: A Polytope Perspective.

Its goal is to demonstrate how the results from the paper above can be obtained using the stochasting_matching package.

It contains in particular:

• Demonstration of the use of the package for theoretical description (graph categorization, etc…);

• the production of all simulation-based results from the paper.

Warning

This section is NOT intended to be self-contained. Please refer to the paper for context and explanations.

• First Steps
  • Categorizing graphs by kernel
    • Bijective case
    • Surjective-only case
    • Injective-only case
    • Nonjective case (not surjective, not injective)
  • Rate solutions
    • Bijective case
    • Surjective-only case
    • Bipartite case
• Polytope analysis
  • Computing kernel basis
    • Examples of 1-D kernels
      • Diamond
      • Unbalanced Kayak Paddle
      • Hypergraphs
    • Examples of 2-D kernels
      • Co-Domino
      • Triamond
  • Vertices
    • Co-domino variations
      • Mix of injective-only and bijective vertices
      • 3 injective-only vertices
      • 3 bijective vertices
      • 5 bijective vertices
    • Pyramid polytope
• Simulations
  • Approaching vertices
    • Preparation
    • Diamond
      • Injective-only vertex
      • Bijective vertex
    • Codomino
      • Injective-only vertex
      • Bijective-only vertex
    • Larger graphs
      • Injective-only vertex
      • Bijective vertex
  • Approaching vertices of hypergraphs
    • Abandonment
    • Nazari & Stolyar example
      • First arrival rates
      • Second arrival rates
  • Flexibility of greedy policies
    • Complete graph
    • Diamond
    • Fish graph
      • Rate limitation lemma
      • Unstable greedy policy lemma
      • Evaluation