Publications by Kenjiro Takazawa

Papers in Submission/Preparation

1. G. Csáji, T. Kiály, K. Takazawa and Y. Yokoi: Popular maximum-utility matching with matroid constraints. arXiv:2407.09798, 2024.
2. Y. Kanaya and K. Takazawa: A faster deterministic approximation algorithm for TTP-2. arXiv:2310.02592, 2023.

Papers in Refereed Journals^♦ and Refereed Conferences^♠

1. K. Takazawa: A unified model of congestion games with priorities: Two-sided markets with ties, finite and non-affine delay functions, and pure Nash equilibria.
   ♠ Proceedings of the 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025), Lecture Notes in Computer Science, to appear. [Acceptance ratio = 37% (26/71)]
2. K. Takazawa: Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyond.
   ♦ Discrete Applied Mathematics, 361 (2025), 226-235.
   ♠ Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), pp. 2495-2497. (Entitled "Pure Nash equilibria in weighted congestion games with complementarities and beyond") [Acceptance ratio = 36% (414/1113)]
3. F. Kiyosue and K. Takazawa: A common generalization of budget games and congestion games.
   ♦ Journal of Combinatorial Optimization, 48 (2024), 24 (18 pp.).
   ♠ Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT 2022), Lecture Notes in Computer Science, 13584, 2022, pp. 258-274. [Acceptance ratio = 41% (34/83)]
   [解説: クリックで展開]
   初の指導修論. 予算ゲームという, 混雑ゲームとよく似た非協力ゲームのモデルについて, 実際どのような関係なのかを解析した論文. 具体的には, 「各プレイヤーの戦略空間がマトロイドの基族である場合に純粋ナッシュ均衡が存在する」という予算ゲームの性質を保ったまま, 予算ゲームとある種の混雑ゲームを共通に一般化するモデルを提案した. 予算ゲームのモデル設定で肝となっている点を抽象化したという感じ. 今まで専門ではなかった分野の会議に採択されてうれしい.
4. Y. Hatajima and K. Takazawa: A note on upgrading the min-max weight of a base of a matroid.
   ♦ JSIAM Letters, 16 (2024), 1-4.
5. Y. Iwamasa, Y. Kobayashi and K. Takazawa: Finding a maximum restricted $t$-matching via Boolean edge-CSP.
   ♠ Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024), Leibniz International Proceedings in Informatics 308, 2024, pp. 75:1-75:15. [Acceptance ratio = 32% (78/247, track A)]
6. K. Takazawa: An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint.
   ♦ Operations Research Letters, 51 (2023), 128-132.
   [解説: クリックで展開]
   M# 凸関数 $f\colon \mathbb{Z}^E \to \mathbb{R}$, 部分集合 $R\subseteq E$ と整数 $k\in \mathbb{Z}$ が与えられて, color-induced budget constraint $x(R)=k$ の下で $f(x)$ を最小化する効率的なアルゴリズム. Gottschalk, Lüthen, Peis, Wierz (JOCO, 2018) がポリマトロイドの基多面体 (M 凸集合) 上の分離凸関数を扱っていたのを, M# 凸関数 (M# 凸集合上の非分離凸関数) に拡張したもの.
   テクニカルには M 凸的にはまったく自然だったのと, M 凸交叉の特殊ケースでもあるので, 面白いかどうかの自信はあまりなかった. しかし, 書いているうちに,

   • 一番シンプルな特殊ケース (weighted matroid intersection の特殊ケースの高速化) が Gabow, Tarjan (J. Algorithms, 1984) によって綿密にやられていた,
   • M# 凸最小化の貪欲アルゴリズム (Murota, Shioura, MOR 1999) の拡張でもある

   ということがはっきりして, 由緒正しい研究といわんばかりのイントロが書けた.
7. K. Natsui and K. Takazawa: Finding popular branchings in vertex-weighted directed graphs.
   ♦ Theoretical Computer Science, 953 (2023), 113799 (13 pp.).
   ♠ Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, 13174, 2022, pp. 303-314. [Acceptance ratio = 34% (30/89)]
   [解説: クリックで展開]
   共著者君の卒論. 先行研究 (重みなし) がきれいに解けていたので, 重みありでも「いけるやろ」と思って卒論のテーマにしたら, 実に大変だった. 共著者君がんばった.
8. M. M. Halldórsson, T. Ishii, K. Makino and K. Takazawa: Posimodular function optimization.
   ♦ Algorithmica, 84 (2022), 1107-1131.
   ♠ Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS 2017), Lecture Notes in Computer Science, 10389, 2017, pp. 437-448. [Acceptance ratio = 45% (49/109)]
   [解説: クリックで展開]
   Magnús M. Halldórsson が RIMS に滞在しているときに, このメンバーで研究したネタ. 劣モジュラ不等式の $X \cup Y, X \cap Y$ を $X \setminus Y, Y \setminus X$ にしたらどうなるのかという話 (たとえばグラフのカット関数). 成果としては, 最小化も最大化も指数回のオラクルが必要とか, ある種の FPT 性とか.
9. K. Takazawa: Notes on equitable partitions into matching forests in mixed graphs and into $b$-branchings in digraphs.
   ♦ Discrete Mathematics and Theoretical Computer Science, 24 (2022).
   ♠ Proceedings of the 6th International Symposium on Combinatorial Optimization (ISCO 2020), Lecture Notes in Computer Science 12176, 2020, pp. 214-224. [Acceptance ratio = 38% (25/66)]
   [解説: クリックで展開]
   Király, Yokoi (arXiv, 2018) を読んで以来ずっと温存していたネタだったが, 2020 年 2 月に, ISCO 2020 の締切が延長になったという, OR 学会のメーリングリストへの F 先生の投稿を見て書く気になって, モントリオールに行くぞと思って投稿した. そして, ISCO 2020 は新型コロナウイルスのため Zoom 開催となった.
   Kiály, Yokoi 論文では, マッチング森への分割の equitability を辺数 (無向辺の本数, 有向辺の本数, その合計の 3 基準) で定義しているが, マッチング森のデルタマトロイド構造 (SIDMA 2014 論文) を思うと被覆している頂点数で equitability を定義するのが良いのではというネタ. 辺数で定義すると 3 つの基準のうち 2 つは差が 2 にならざるをえないことがある (しかし 2 で収まるのがえらい) が, 頂点数で定義すると差が 1 で収まる.
   これだけだと寂しいので, $b$-branching への equitable partition も考えて, 合わせ技で論文にした. $b$-branching では, 辺数と各頂点での入次数の $n+1$ 個の equitability をすべて同時に達成できる.
10. S. Fujishige, T. Király, K. Makino, K. Takazawa and S. Tanigawa: Minimizing submodular functions on diamonds via generalized fractional matroid matchings.
    ♦ Journal of Combinatorial Theory, Series B, 157 (2022), 294-345.
[解説: クリックで展開]
Tamás Király が RIMS に滞在しているときに, このメンバーで研究したネタ. 質・量ともにヘビーで, 査読に非常に時間がかかった.
11. Y. Iwamasa and K. Takazawa: Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications.
    ♦ Mathematical Programming, Series A, 194 (2022), 229-256.
    ♠ Proceedings of the 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), Lecture Notes in Computer Science 12337, 2020, pp. 156-167. [Acceptance ratio = 45% (37/83)]
    [解説: クリックで展開]
    Lendl, Peis, Timmermans (arXiv, July 2019) の論文を見て, 問題ごとの多項式時間可解性と NP 困難性の要因を直感的に理解することを動機として, 目的関数を M 凸関数に拡張した. 最終的に, けっこう応用範囲の広い枠組になった.
    2019 年 8 月の COSS で, M-convex intersection のプロである岩政さんに声をかけ, テクニカルな箇所をやってもらった. また, 2019 年 9 月の Cargèse Workshop で, András Frank も同じ論文に興味を持っていることを知り, その後たびたび成果を報告した (あわよくば共著にと思っていたが, 結局ならなかった).
12. K. Takazawa: The $b$-bibranching problem: TDI system, packing, and discrete convexity.
    ♦ Networks, 79 (2022), 32-46.
    [解説: クリックで展開]
    $b$-bibranching という, bibranching と $b$-branching の共通の一般化を提案した論文. Bibranching や $b$-branching に関する結果の拡張として, shortest $b$-bibranching problem の完全双対整数性をもつ LP 表現と M$^\natural$凸劣モジュラ流表現と, 詰込定理を与えた. Bibranching の制約のうち, 次数は 1 から $b(v)$ に一般化しているが, 連結性は 1 のままにするとよいというところが, テクニカルには面白いと思う.
    JCCA 2017 で Y さんの話を聞いて, supermodular coloring で論文を書きたいと思ったのと bibranching の詰め込みが supermodular coloring で証明できることを知ったのとがあり, ちょうどそのとき $b$-branching の論文を書き始めていたので, 何とか一般化できるだろうということで何とかした. 結果的に, $b$-bibranching の詰め込みが supermodular coloring を非自明に使って証明できたので, 個人的には大満足. そういった意味では, 「100％ 趣味で書いた論文」といえなくもない.
    LP 表現と M$^\natural$凸劣モジュラ流表現のそれぞれから shortest $b$-bibranching の多項式時間アルゴリズムが得られるが, bibranching も $b$-branching も直接的な組合せ的アルゴリズムがあるので, $b$-bibranching に対しても作れそうなものではある.
13. S. Matsuura and K. Takazawa: An improved heuristic algorithm for the maximum benefit Chinese postman problem.
    ♦ RAIRO-Operations Research, 56 (2022), pp. 1283-1291.
    
    [解説: クリックで展開]
    指導卒論で初の海外ジャーナル採択論文. 最大利益郵便配達人問題について, 特定の場合にのみ適用可能だった Pearn--Wang のヒューリスティックアルゴリズムを, $T$-join を用いて精緻化 & 単純化し, かつ, Corberán et al. の分枝カット法で使われていた手法を用いて一般の場合に適用できるように拡張したもの. Pearn--Wang は実はほぼほぼ MST と $T$-join (ほぼほぼ Christrofides) で, Corberán et al. の手法もコロンブスの卵なので, シンプルなのが良い. それにしても, まさかヒューリスティックで論文を書くことになるとは (近似率わからん) & 計算機実験なしで accept までこぎつけられて助かった (サンキュー Y.Y.).

14. K. Takazawa: Excluded $t$-factors in bipartite graphs: A unified framework for nonbipartite matchings, restricted 2-matchings, and matroids.
    ♦ SIAM Journal on Discrete Mathematics, 36 (2022), pp. 702-727.
    ♠ Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017), Lecture Notes in Computer Science 10328, 2017, pp. 430-441. [Acceptance ratio = 29% (36/125)]
    
    [解説: クリックで展開]
    MFCS 2016 から帰ってきて, そのネタを 2-マッチングから t-マッチングに拡張しようかとなんとなく考えていたら, t=1 のときに even factor が表現できることに気付いて, なんとなくどころか一気にテンションが上がって書いた論文.
    以下を含む枠組を提案している：

    • 一般グラフのマッチング,
    • Even factor,
    • 2 部グラフの square-free 2-マッチング,
    • Triangle-free 2-マッチング (の重複度 2 を含む版).
    • Arborescence

    たとえば，

    • 2 部グラフにおける枠組で, 一般グラフのマッチングが表現できている,
    • Even factor と square-free 2-マッチングは似たアルゴリズムで解けると Gyula Pap が (一つの論文で) 書いていたのだが, その裏付けを与えている,
    • 重み付き even factor の「各奇閉路 $C$ で $w(C)=w(\bar{C})$」の仮定と, 重み付き square-free 2-マッチングの「各 square で重みが vertex-induced」の仮定は本質的に同じ，
    • 一般グラフのマッチングの blossom constraint と TSP の subtour elimination constraint は同じ構造をしている

    といったあたりが面白いと思う.
    書こうと思ってから IPCO に投稿するまでは 2 か月余りだったが, (学生の頃に) even factor を研究していなかったらこのネタに至らなかっただろうから, ある意味「この論文を書くのに, 10 年かかった」といえる (?).
15. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings.
    ♦ Japan Journal of Industrial and Applied Mathematics, 38 (2021), 141-161.
    [解説: クリックで展開]
    Bonn での講演の準備をしていたらそれに関連するネタを思い付いたという M 師匠からメモを送りつけていただいたことから始まった研究. "Two formulations for shortest bibranchings" とは, LP 表現と M$^\natural$凸劣モジュラ流表現のこと (後者は JIAM 2012 の論文). 本論文の主結果は,

    1. M$^\natural$凸劣モジュラ流表現は, LP 表現に Benders 分解を施すと得られる,
    2. 一方の表現の主双対最適解から, 他方の表現の主双対最適解が構成できる

    というもの. JIAM 2012 のときは, LP 表現とは独立に, 組合せ的な議論だけで M$^\natural$凸劣モジュラ流表現を導出したのだが, 実は両者は繋がっていたという点が味わい深い. 個人的には, 学生の頃に某先輩の研究で名前だけは聞いたことがあった Benders 分解について自分も論文に書くことにな (るとは思わなか) ったという点も味わい深い.
    余談だが, 論文の TeX ファイル名を "murotakazawa.tex" にしたら M 師匠から好評だった (「murota + takazawa」というつもりしかなかったのだが, あちら側からは「murotakaz + ノイズ」とも見えるらしい).
16. N. Kakimura, N. Kamiyama and K. Takazawa: The $b$-branching problem in digraphs.
    ♦ Discrete Applied Mathematics, 283 (2020), 565-576.
    ♠ Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics 117, 2018, pp. 12:1-12:15. [Acceptance ratio ≤ 40% (84/210)]
    
    [解説: クリックで展開]
    Arborescence algorithm を拡張できる matroid intersection のクラスはないかという動機で書いた論文. 本論文で提案した $b$-branching とは, branching における「各頂点 $v$ の入次数が 1 以下」という制約を, 「各頂点 $v$ の入次数が $b(v)$ 以下」という制約に一般化したもの ($b(v)$ は任意の正整数). つまり, マッチングに対する $b$-マッチングに相当する.
    もう一つのマトロイド (branching のグラフ的マトロイドの分) については, $|F[X]| \leq b(X)-1\ (X \subseteq V)$ で定まる疎性マトロイドと定義することにより, arborescence algorithm が拡張できることを証明した. それに加えて, Edmonds の有向木詰込定理の拡張も与え, さらに, それを用いて $b$-branching polytope の整数分解性 (integer decomposition property) も証明している. というわけで, この疎性マトロイドを用いた定義こそが "$b$-branching" として正当なものと言えると思う.
    JH 2017 で arborescence についての発表を聞きまくっていたら, 「あれ？ 自分の発表 (IPCO 2017 論文) のアルゴリズムって arborescence algorithm と同じじゃね？」と思って, arborescence 的なアルゴリズムを設計できる matroid intersection のクラスはないかとその場にいた垣村さんに相談したところ, やはりその場にいた神山さんがそのような研究をしていると教えていただき, エトヴェシュ大学の食堂で３人でディスカッションをしたというのが始まり. Yet another KKT!

17. M. Kawasaki and K. Takazawa: Improving approximation ratios for the clustered traveling salesman problem.
    ♦ Journal of the Operations Research Society of Japan, 63 (2020), 60-70.
    
    [解説: クリックで展開]
    指導学生の論文を初めて論文誌に投稿して, 採録された. めでたい！
18. S. Fujishige, K. Takazawa and Y. Yokoi: A note on a nearly uniform partition into common independent sets of two matroids.
    ♦ Journal of the Operations Research Society of Japan, 63 (2020), 71-77.
    
    [解説: クリックで展開]
    DM 2019 論文 (の arXiv 版) を読んでくださった F 先生のアイディアによる論文. ポリマトロイド理論を使うと, 分割した共通独立集合の大きさの差を高々 1 にできる.
19. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids.
    ♦ Discrete Mathematics, 342 (2019), 2002-2011.
    
    [解説: クリックで展開]
    Bipartite edge-coloring に対する Kőnig の定理を matroid intersection に拡張する (台集合を共通独立集合に分割する) というネタ. これと同様に bipartite edge-coloring の一般化である supermodular coloring は generalized polymatroid を使って Kőnig の定理が拡張できるので, そのアプローチを使おうという論文.
    Contribution としては, それぞれのマトロイドが

    1. laminar matroid ($\subseteq$ strongly base orderable matroid),
    2. Kotlar and Ziv (2005) の条件をみたすマトロイド (2 種類)

    のいずれかである場合に, Kőnig の定理を拡張できた. 既存研究で扱っているのは, 「両方のマトロイドが 1.」, 「両方のマトロイドが 2.」であるケースだけだったが, 本研究では「一方のマトロイドが 1., もう一方のマトロイドが 2.」というケースを扱えたのが新しい. また, Kotlar and Ziv (2005) で別々の証明が与えられていた 2 種類のマトロイドを統一的に扱えた (≒ Kotlar and Ziv の 2 条件は, generalized polymatroid アプローチで扱える 2 条件だったと明らかになった) のが面白いと思う.
20. K. Takazawa: Generalizations of weighted matroid congestion games: Pure Nash equilibrium, sensitivity analysis, and discrete convex function.
    ♦ Journal of Combinatorial Optimization, 38 (2019), 1043-1065.
    ♠ Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC 2019), Lecture Notes in Computer Science, 11436, pp. 594-614.
    [解説: クリックで展開]
    Harks, Klimm, Peis (SIOPT 2018) の論文 (ポリマトロイド混雑ゲームにおけるナッシュ均衡の存在) を見て, 「これ絶対 M 凸関数に拡張できるやろ」と思って考えだしたら, Key Lemma (M 凸最小化の感度分析) の証明までは拡張できたものの, 最後のナッシュ均衡の存在の証明が拡張できなかったので, Key Lemma までと, 混雑ゲームの別の二つの一般化との合わせ技で論文にした.
    この成果を引っさげて (というか, 最後の証明の完成を目指して), 2020 年 3 月に Britta Peis を訪問する予定だったが, 新型コロナウイルスのためキャンセルになった.
21. K. Takazawa: Decomposition theorems for square-free 2-matchings in bipartite graphs.
    ♦ Discrete Applied Mathematics, 233 (2017), pp. 215-223.
    ♠ Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Lecture Notes in Computer Science 9224, 2016, pp. 373-387. [Acceptance ratio = 41% (32/79)]
    [解説: クリックで展開]
    グルノーブルにいた頃, コルシカ島でのワークショップで会った I 師匠に「square-free 2-マッチングの DM 分解ってできないの？」と聞かれて考え始めた. Horizontal tail, vertical tail とその補集合の三つへの分解は比較的すんなりできたが, 最小化集合の束構造がよくわからなくて研究が数か月難航した. 結局, 束構造はただちには得られないだろうということで, 三つへの分解＋αという DM 分解と Edmonds-Gallai 分解の合いの子のような形にまとめて論文にした. その後に一般化をしたりして研究を展開させた今になって振り返ると, この判断で良かったのではと思う. 久しぶりの accept だったのと, これをきっかけに IPL 2016 論文・DisOpt 2017 論文・IPCO 2017 論文を書くことができたので, この論文にはいろいろと助けられた.
22. K. Takazawa: Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs.
    ♦ Discrete Optimization, 26 (2017), pp. 26-40.
    ♠ Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics 58, 2016, pp. 87:1-87:14. [Acceptance ratio ≤ 38% (84/220)]
    [解説: クリックで展開]
    Square-free 2-マッチングの分解定理 (DAM 2017 論文) で, 禁止構造において重要なのは square であることではなく, factor-criticality にあたる性質だと気付き, 禁止サイクルがこの factor-criticality をもっていれば効率的に解けるということで書いた論文. たとえば, "chord を 2 本以上もつ $C_6$"-free 2-マッチングの辺数最大化が解けるようになった ($C_6$-free 2-マッチングの辺数最大化は NP 困難).
    サーベイをする中で, この factor-criticality (の十分条件) が, グラフ理論では "Hamilton-laceable" とよばれていると知り, RIMS の図書室に古い論文を取り寄せていただいたのをよく覚えている.
23. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsack problem.
    ♦ Theoretical Computer Science, 699 (2017), pp. 53-62.
    ♠ Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016), 2016, pp. 25-33.
[解説: クリックで展開]
Matuschke, Skutella, Soto (SODA 2015) で導入されたロバスト独立システムに対する混合戦略を, ナップサック問題について設計 + そのロバスト比がほぼタイトとなる上界を与えたというもの. 2014 年度中に京都から東大に何度か押しかけ, 小林さんとディスカッションをしてできた論文.
24. K. Takazawa: A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs.
    ♦ Information Processing Letters, 116 (2016), pp. 550-553.
    [解説: クリックで展開]
    3 辺連結 3 正則 2 部グラフにおける最小全域 2 辺連結部分グラフの 7/6 近似アルゴリズム. SIDMA 2013 論文の中で, 3 辺連結 3 正則グラフでの 6/5 近似アルゴリズムを与えていて, これを 2 部グラフに限定して近似率を改良したもの. グルノーブルにいた頃は Barnette グラフ (3 連結 3 正則平面 2 部グラフ) で 7/6 近似を考えていてうまくいかなかったのだが, 実は平面性は必要なかったという.
    最近, 3 辺連結 3 正則グラフ (2 部性なし) でも 7/6 近似解の存在が示されたもよう→link
25. K. Takazawa: Optimal matching forests and valuated delta-matroids.
    ♦ SIAM Journal on Discrete Mathematics, 28 (2014), pp. 445-467.
    ♠ Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), Lecture Notes in Computer Science 6655, 2011, pp. 404-416. [Acceptance ratio = 30% (33/110)]
    [解説: クリックで展開]
    Branching のマトロイド構造に基づく論文 2 本のうちの 1 本 (もう 1 本は JIAM 2012). Schrijver による branching や matching forest の交換可能性の証明を離散凸の目をもって読むと, 付値デルタマトロイドが直ちに導かれる. さらに, この branching のマトロイド構造をもって Giles の matching forest アルゴリズムを読むと, 縮約のルールを変更したくなる, という内容. それとは別に, Giles の matching forest アルゴリズムに Gabow の weighted matching に対する手法を適用すると計算量が改善できる, というネタと合わせ技で 1 本の論文にした.
26. S. Boyd, S. Iwata and K. Takazawa: Finding 2-factors closer to TSP tours in cubic graphs.
    ♦ SIAM Journal on Discrete Mathematics, 27 (2013), pp. 918-939.
    [解説: クリックで展開]
    2010 年の春に RIMS に滞在していた Sylvia Boyd と, そのホストだった I 先生との共著論文.

    1. 2 辺連結 3 正則グラフにおける, すべての 3 辺カットと交わる 2-因子の中で最小重みのもの,
    2. 2 辺連結 3 正則グラフにおける, すべての 3 辺カットおよび 4 辺カットと交わる 2-因子,
    3. 3 辺連結 3 正則グラフにおける, 辺数 $6n/5$ 以下の最小全域 2 辺連結部分グラフ

    を求めるアルゴリズムを設計した (いずれもハミルトン閉路の緩和). おもに, カット関数の劣モジュラ性を使った議論は I 先生が, 3. のアルゴリズムの泥臭い部分は Sylvia と私で考えた (と記憶している).
27. K. Takazawa: Shortest bibranchings and valuated matroid intersection.
    ♦ Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561-573.
    [解説: クリックで展開]
    Branching のマトロイド構造に基づく論文 2 本のうちの 1 本 (もう 1 本は SIDMA 2014). Branching の離散凸構造に注目すると, 最小重み bibranching 問題が付値マトロイド交わり問題に帰着されるという内容. 帰着する前の問題も帰着した後の問題も {0,1} の世界 (付値マトロイドの世界) の中にあるのだが, 証明の中では Z の世界 (M$^\natural$凸関数の世界) を通っているのがニクい (なので, 室田・高澤論文 (2017) では M$^\natural$凸劣モジュラ流表現と書いている).
    この論文では組合せ的な議論のみによって付値マトロイド交わり表現を得たが, LP 表現に Benders 分解を施すことによっても得られることを後に室田・高澤論文 (2017) で示した.
28. Y. Kobayashi, J. Szabó and K. Takazawa: A proof of Cunningham's conjecture on restricted subgraphs and jump systems.
    ♦ Journal of Combinatorial Theory, Series B, 102 (2012), pp. 948-966.
29. K. Takazawa: A weighted independent even factor algorithm.
    ♦ Mathematical Programming, Series A, 132 (2012), pp. 261-276.
    [解説: クリックで展開]
    Weighted even factor algorithm (Math Program 2008) と Independent even factor algorithm (SIDMA 2008) を基にした, weighted independent even factor algorithm.

    • やる前はやればできるだろうと思っていたが, やってみたら結構苦労した.
    • これで even factor の論文を書くのは最後だろうと思っていたが, IPCO 2017 の論文で even factor が登場した.

    研究は, やってみないとわからないというお話.
30. K. Takazawa: Even factors: Algorithms and structure.
    ♦ Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu, B23 (2010), pp. 233-252.
    [解説: クリックで展開]
    RIMS プロジェクト研究「離散構造とアルゴリズム」 研究集会の招待講演の論文化. 内容は, even factor のサーベイ.
    高名な講演者が並ぶ中で自分は D2 のヒヨッコだったので, 講演はかなりのプレッシャーだった.
31. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity.
    ♦ Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139-161.
32. K. Takazawa: A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite graphs.
    ♦ Mathematics of Operations Research, 34 (2009), pp. 351-362.
    ♠ Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), Lecture Notes in Computer Science 5035, 2008, pp. 62-76. [Acceptance ratio = 34% (32/95)]
    [日本オペレーションズ・リサーチ学会 第 5 回 文献賞奨励賞 受賞]
    [解説: クリックで展開]
    2 部グラフにおける square-free 2-マッチングについて, 重みなし版のアルゴリズム (Pap 2007) と LP 表現 (Makai 2007) に基いて, 重み付き版のアルゴリズムを設計して, さらに t-マッチングにも拡張したもの. 最小費用流アルゴリズムを拡張したのだが, 縮約した部分の取り扱いに苦労して, RIMS の周辺を歩き回りながら考えること 1〜2 か月くらいの末に解決にたどり着いた. 重みなし版の単純化もしているのと, ほどほどに非自明な拡張ができたのとで, 割と気に入っている論文.
    IPCO での発表の後, KK 先生から "Good job, good job" とのねぎらいのお言葉をいただいた.
33. K. Takazawa: A weighted even factor algorithm.
    ♦ Mathematical Programming, Series A, 115 (2008), pp. 223-237.
    [日本オペレーションズ・リサーチ学会 第 5 回 文献賞奨励賞 受賞]
    [解説: クリックで展開]
    初投稿論文. 一般グラフのマッチングの一般化である even factor について, 重みなし版のアルゴリズム (Pap 2007) と LP 表現 (Király & Makai 2004) に基いて, 重み付き版のアルゴリズムを設計したもの. 初期解の定め方がなかなか思い付かなかったのだが, ある日夕飯を食べて研究室に戻って考えていたら急にひらめいた (このとき, 大声を上げて周囲の人々を驚かせてしまったらしい).
    一回目の査読レポートが来る直前くらいにアルゴリズムのバグを発見して落ち込んでいたのだが, M 師匠の「我々の仕事はミスをしても人が死ぬわけじゃないからねぇ」という励ましに大いに救われ, 涙ながらに修正をした.
34. S. Iwata and K. Takazawa: The independent even factor problem.
    ♦ SIAM Journal on Discrete Mathematics, 22 (2008), pp. 1411-1427.
    ♠ Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007, pp. 1171-1180. [Acceptance ratio = 36% (139/382)]
    [解説: クリックで展開]
    Even factor とマトロイド交わりの共通の一般化 (independent even factor) について, 最大最小定理, 組合せ的アルゴリズム, 正準分解を与えたもの. マトロイドの "shrink" という (contraction とは異なる) 演算を導入したのが本人としては楽しかった. この演算を使うことにより, アルゴリズムは straightforward に書けたものの, 最適性の証明 (≒最大最小定理の設計) で苦労していたのだが, I 師匠に状況を話したらいつの間にか解決されていた.
    余談だが, SODA 会期中の夕食でアメリカンサイズのスペアリブ 2 人前を平らげたことにより, N 先生から「博士 (リブ)」の称号をいただいた.

Informal Publications

1. G. Csáji, T. Kiály, K. Takazawa and Y. Yokoi: Popular maximum-utility matching with matroid constraints. The 7th International Workshop on Matching Under Preferences (MATCH-UP 2024), 2024, abstract, to appear.
2. Y. Kanaya and K. Takazawa: A faster deterministic approximation algorithm for TTP-2. The 8th International Symposium on Combinatorial Optimization (ISCO 2024), 2024, extended abstract.

3. K. Takazawa: $b$-branchings in digraphs: Branchings with higher indegree. Proceedings of the 11th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (HJ 2019), 2019, pp. 79-88.
4. K. Takazawa: Excluded $t$-factors in bipartite graphs: A unified framework for nonbipartite matchings and restricted 2-matchings. Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017), 2017, pp. 483-492.
5. K. Takazawa: Structure theorems for square-free 2-matchings in bipartite graphs. Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2015), 2015, pp. 69-78.
6. Y. Kobayashi and K. Takazawa: Square-free 2-matchings in bipartite graphs and jump systems. Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2009), 2009, pp. 187-197.
7. K. Takazawa: A weighted independent even factor algorithm. Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2009), 2009, pp. 361-371.
8. K. Takazawa: A weighted even factor algorithm. Proceedings of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2007), 2007, pp. 43-52.

Technical Reports/Preprints

1. K. Takazawa: A unified model of congestion games with priorities: Two-sided markets with ties, finite and non-affine delay functions, and pure Nash equilibria. arXiv:2407.12300, 2024.
2. G. Csáji, T. Kiály, K. Takazawa and Y. Yokoi: Popular maximum-utility matching with matroid constraints. arXiv:2407.09798, 2024.
3. K. Takazawa: Pure Nash equilibria in weighted congestion games with complementarities and beyond. arXiv:2401.03861, 2024.
4. Y. Iwamasa, Y. Kobayashi and K. Takazawa: Finding a maximum restricted $t$-matching via Boolean edge-CSP. arXiv:2310.20245, 2023.
5. Y. Kanaya and K. Takazawa: A faster deterministic approximation algorithm for TTP-2. arXiv:2310.02592, 2023.
6. K. Natsui and K. Takazawa: Finding popular branchings in vertex-weighted digraphs. arXiv:2110.03460, 2021.
7. K. Takazawa: Notes on equitable partitions into matching forests in mixed graphs and into $b$-branchings in digraphs. arXiv:2003.10774, 2020.
8. Y. Iwamasa and K. Takazawa: Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications. arXiv:2003.02424, 2020.
9. S. Fujishige, K. Takazawa and Yu Yokoi: A note on a nearly uniform partition into common independent sets of two matroids. arXiv:1909.13261, 2019.
10. K. Takazawa: M-convexity of the minimum-cost packings of arborescences. arXiv:1805.08381, 2018.
11. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids. arXiv:1805.05528, 2018.

12. K. Takazawa: The $b$-bibranching problem: TDI system, packing, and discrete convexity. arXiv:1802.03235, 2018.

13. N. Kakimura, N. Kamiyama and K. Takazawa: The $b$-branching problem in digraphs. arXiv:1802.02381, 2018.

14. K. Takazawa: Excluded $t$-factors in bipartite graphs: Unified framework for nonbipartite matchings, restricted 2-matchings, and matroids. arXiv:1708.00582, 2017.
15. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings. arXiv:1706.02029, 2017.
16. K. Takazawa: Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs. RIMS Preprint, RIMS-1839, Kyoto University, 2015.
17. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsack problem. RIMS Preprint, RIMS-1833, Kyoto University, 2015.
18. K. Takazawa: Approximation algorithms for the minimum 2-edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs via restricted 2-factors. RIMS Preprint, RIMS-1826, Kyoto University, 2015.
19. K. Takazawa: Decomposition theorems for square-free 2-matchings in bipartite graphs. RIMS Preprint, RIMS-1813, Kyoto University, 2015.
20. S. Fujishige, T. Király, K. Makino, K. Takazawa and S. Tanigawa: Minimizing submodular functions on diamonds via generalized fractional matroid matchings. EGRES Technical Reports, TR-2014-14, Egerváry Research Group, 2014. (See also RIMS Preprint, RIMS-1812, Kyoto University, 2015.)
21. S. Boyd, S. Iwata and K. Takazawa: Covering cuts in bridgeless cubic graphs. RIMS Preprint, RIMS-1731, Kyoto University, 2011.
22. K. Takazawa: Optimal matching forests and valuated delta-matroids. RIMS Preprint, RIMS-1718, Kyoto University, 2011.
23. Y. Kobayashi, J. Szabó and K. Takazawa: A proof to Cunningham's conjecture on restricted subgraphs and jump systems. EGRES Technical Reports, TR-2010-04, Egerváry Research Group, 2010.
24. K. Takazawa: A weighted independent even factor algorithm. Mathematical Engineering Technical Reports, METR 2009-15, University of Tokyo, 2009.
25. Y. Kobayashi and K. Takazawa: Square-free 2-matchings in bipartite graphs and jump systems. Mathematical Engineering Technical Reports, METR 2008-40, University of Tokyo, 2008. (See also RIMS Preprint, RIMS-1640, Kyoto University, 2008.)
26. K. Takazawa: A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite graphs. Mathematical Engineering Technical Reports, METR 2008-07, University of Tokyo, 2008. (See also RIMS Preprint, RIMS-1621, Kyoto University, 2008.)
27. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity. Mathematical Engineering Technical Reports, METR 2007-36, University of Tokyo, 2007. (See also RIMS Preprint, RIMS-1595, Kyoto University, 2007.)
28. S. Iwata and K. Takazawa: The independent even factor problem. Mathematical Engineering Technical Reports, METR 2006-24, University of Tokyo, 2006.
29. K. Takazawa: A weighted even factor algorithm. Mathematical Engineering Technical Reports, METR 2005-17, University of Tokyo, 2005.

共著・共訳

1. R. セジウィック (著), 田口東, 高松瑞代, 高澤兼二郎 (訳): セジウィック: アルゴリズム C 第 5 部, グラフアルゴリズム, 近代科学社, 2021 年 11 月.

2. 高澤兼二郎: マッチング. 薩摩順吉, 大石進一, 杉原正顕 (編), 応用数理ハンドブック, 朝倉書店, 2013 年 11 月, pp. 288-289.

学位論文

• [博士論文] Combinatorial Algorithms for Generalized Matching Problems (マッチング問題の一般化に対する組合せ的アルゴリズム), 東京大学, 2010 年 3 月.
  • 指導教員: 室田一雄 教授.

• [修士論文] A Unified Approach to Combinatorial Algorithms for Matchings and Matroids (マッチングとマトロイドの組合せ的アルゴリズムへの統一的アプローチ), 東京大学, 2007 年 3 月.
  • 指導教員: 室田一雄 教授, 岩田覚 助教授.
  • 日本オペレーションズ・リサーチ学会 第 25 回 学生論文賞 受賞.
  • 東京大学大学院情報理工学系研究科長賞 受賞.