Publications by Kenjiro Takazawa

Publications by Kenjiro Takazawa


Papers in Submission/Preparation

  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. 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. 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.
  2. K. Takazawa: Pure Nash equilibria in weighted congestion games with complementarities and beyond.
    Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), pp. 2495-2497. [Acceptance ratio = 36% (414/1113)]
  3. 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), to appear. [Acceptance ratio = 32% (78/247, track A)]
  4. K. Takazawa: An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint.
    Operations Research Letters, 51 (2023), 128-132.
  5. K. Natsui and K. Takazawa: Finding popular branchings in vertex-weighted directed graphs.
    Theoretical Computer Science, 953 (2023), 113799.
    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)]
  6. 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)]
  7. 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)]
  8. 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.
  9. 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)]
  10. K. Takazawa: The $b$-bibranching problem: TDI system, packing, and discrete convexity.
    Networks, 79 (2022), 32-46.
  11. S. Matsuura and K. Takazawa: An improved heuristic algorithm for the maximum benefit Chinese postman problem.
    RAIRO-Operations Research, 56 (2022), pp. 1283-1291.

  12. 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)]
  13. F. Kiyosue and K. Takazawa: A common generalization of budget games and congestion games.
    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)]
  14. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings.
    Japan Journal of Industrial and Applied Mathematics, 38 (2021), 141-161.
  15. 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)]

  16. 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.
  17. 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.
  18. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids.
    Discrete Mathematics, 342 (2019), 2002-2011.
  19. 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.
  20. 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)]
  21. 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)]
  22. 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.
  23. 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.
  24. 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)]
  25. 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.
  26. K. Takazawa: Shortest bibranchings and valuated matroid intersection.
    Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561-573.
  27. 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.
  28. K. Takazawa: A weighted independent even factor algorithm.
    Mathematical Programming, Series A, 132 (2012), pp. 261-276.
  29. K. Takazawa: Even factors: Algorithms and structure.
    Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu, B23 (2010), pp. 233-252.
  30. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity.
    Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139-161.
  31. 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 回 文献賞奨励賞 受賞]
  32. K. Takazawa: A weighted even factor algorithm.
    Mathematical Programming, Series A, 115 (2008), pp. 223-237.
    [日本オペレーションズ・リサーチ学会 第 5 回 文献賞奨励賞 受賞]
  33. 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)]

Informal Publications

Conference Proceedings

  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 月.

高澤のホームに戻る