重み付きマッチング概観

この記事は「数理最適化 Advent Calendar 2020」 3 日目の記事です．*1
2 日目は @taka_horibe さんによる「凸最適化の概要と主双対内点法のアルゴリズムの解説」です．
4 日目は @kievdhia さんによる「確率計画法とその周辺の紹介」です．

今回は数理最適化ということで，線形計画と関連が深い組合せ最適化の話を書こうと思います．具体的には，グラフのマッチング問題に関する話を（技術的には深入りせずに）書きます．キーワードを散りばめておきますので，興味を持って深く知りたいという方は，ぜひ専門書 *2 を手に取って勉強してみてください．

線形計画に関連する部分では，線形計画に関する基礎知識を仮定します．また，グラフやマッチング等に関しては，一昨年のアドカレや昨年のアドカレの記事が参考になるかと思います．以下では，入力グラフの頂点数と枝数をそれぞれ n と m で表します．

*1:今年は何故か一年ぶりの更新とはなりませんでしたね．

*2:たとえば，以下の書籍がオススメで，この記事の内容の大部分はこちらに包含されています．
A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. (ISBN: 9783540443896)

続きを読む

Manga Market が解けるまで

今日解いた以下の問題がとてもおもしろかったので，解けるまでの思考を書いてみます．解説するというほどではありませんし，めっちゃネタバレするのでご注意ください．

問題概要

店 i に時刻 t に訪れると，買い物するのに (a_i t + b_i) 時間かかります（ a_i, b_i は非負整数）．店間の移動（最初の店の訪問を含む）には 1 時間かかります．時刻 0 から始めて時刻 T までに買い物を終えるとすると，最大いくつの相異なる店で買い物できますか？

続きを読む

群ラベル制約付き最短路問題

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 4 日目の記事です．*1
3 日目は @921603 さんによる「Proximity search：列挙アルゴリズムの新たな構築手法」です．
5 日目は @TsuMakoto さんによる「IDA* with Pattern Databaseでパズルを解く」です．

グラフにおける最短路問題は組合せ最適化の古典的な問題ですよね．今回は，その制約付きの変種に対する効率的なアルゴリズムを紹介したいと思います．元ネタは，来年 1 月に開催される SODA という離散アルゴリズムの国際会議に採択されている以下の論文です．

Yutaro Yamaguchi: A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1923‒1932.  (Link) *2

奇しくも著者の方とイニシャルが同じ (Y.Y.) でした．運命的ですね．

*1:ブログとしてはちょうど一年ぶりの更新，わかりやすいですね．

*2:その後，改良版がリリースされているようです．すごいですね！
Yoichi Iwata, Yutaro Yamaguchi: Finding a Shortest Non-zero Path in Group-Labeled Graphs. arXiv:1906.04062.  (Link)

続きを読む

マトロイド共通基分割に関する反例

この記事は「反例」アドベントカレンダー 4 日目の記事です．本ブログは別のアドベントカレンダー用に昨日誕生したものですが，せっかくなのでもう 1 つぐらい記事を書いてみようと思います．

続きを読む

Double Counting による Erdős–Ko–Rado 定理の証明

この記事は「好きな証明」アドベントカレンダー 3 日目の記事です．*1

何かを数えるとき，数え間違いを防ぐために，複数の方法で数えてみるというテクニックがありますよね．数学でもこれに似た手法が使われることがあり，同じ対象を 2 通りの方法で数えることにより，その数を通じた関係式を導く技法を Double Counting と呼びます．

たとえば，簡単な例として，非負の整数 n に対して

\displaystyle\sum_{k = 0}^n \binom{n}{k} = 2^n

という等式を示してみましょう．ここで，\binom{n}{k} は {}_nC_k とも書かれる二項係数で，「n 個の異なる物から k 個を選ぶ選び方の総数」に等しい値です．すると左辺は，その場合の数を，あり得る範囲のすべての k に関して足し合わせたものになっています．k の値が違えば同じ組合せが選ばれることも無いので，「n 個の異なる物からいくつかを選ぶ選び方の総数」を漏れなくダブりなく数えた式になっています．一方右辺は，「n 個の物それぞれに関して選ぶか選ばないか（2 通り）を決めることと，選ぶ物の組合せを決めることは同じである」という視点で，同じ場合の数を漏れなくダブりなく数えた式です．したがって，等式の両辺は，同じ対象を異なる方法で数えた式であるので，その値は等しいということが言えます．

*1:この記事を書くために Hatena Blog を始めました．今後記事が増えるかどうかは未定です．

続きを読む