Combinatorial Optimization

• Combination Optimization: Finding the best combination structure that satisfies certain conditions based on a specific criterion.
• Matching Problem:
  • Bipartite Graph Matching:
    • Vertex Covering Set: A set of vertices that covers all edges, meaning at least one vertex from each edge is included.
    • Theorem: The maximum number of edges in a matching is equal to the minimum number of vertices in a covering set (only in bipartite graphs).
    • In other words, to verify a matching with k edges, we can check if it is greater than or equal to max or less than or equal to min.
    • To find the matching with the maximum number of edges, we need to search for a covering set with k vertices or a matching with k+1 edges.
      • To find a matching with k+1 edges, we search for an “augmenting path” (changing 0-1-0 to 1-0-1).
  • General Graph Matching:
    • There is a generalized version of the above theorem.
      • After selecting vertices, we use the remaining vertices that do not cover them.
    • When searching for an augmenting path, if we find an odd-length cycle, it means we can reach any vertex from any other vertex.
      • This is called a “blossom”.
      • It can be treated as a single vertex.
      • By contracting it and finding an augmenting path, we can maximize the number of matchings.
    • The algorithmic approach is the same as in bipartite graphs.
• Shortest path search with even-odd constraints can be solved using weighted matching.
  • The graph is divided into two layers, and matching is performed.
• There is also a technique that applies blossom contraction in Dijkstra’s algorithm.
  • It can find the shortest odd-length path.
  • If the start and end are included in a blossom, it is expanded.

---

• Minimum Spanning Tree Problem and Traveling Salesman Problem are similar.
  • However, the former can be solved optimally with a greedy algorithm, while the latter cannot.
• There are problems that are easier to solve and problems that are harder to solve.
  • Easier problems: Creating a general framework (Matroids).
  • Harder problems: Approximation algorithms or heuristics.
    • Sometimes the methods used for easier problems can be applied.
• http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H22-iwata.pdf
• Matching Problem
• Perfect Matching: Creating a set of pairs using all the vertices.
• Matching problem and Traveling Salesman Problem are similar. (Information Science Expert)