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.
7. K. Natsui and K. Takazawa: Finding popular branchings in vertex-weighted digraphs.
   ♦ 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)]
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, pp. 214-224. [Acceptance ratio = 38% (25/66)]
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.
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, pp. 156-167. [Acceptance ratio = 45% (37/83)]
12. K. Takazawa: The $b$-bibranching problem: TDI system, packing, and discrete convexity.
    ♦ Networks, 79 (2022), 32-46.
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.

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)]
    

15. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings.
    ♦ Japan Journal of Industrial and Applied Mathematics, 38 (2021), 141-161.
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)]
    

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.
    
19. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids.
    ♦ Discrete Mathematics, 342 (2019), 2002-2011.
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.
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)]
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)]
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.
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.
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)]
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.
27. K. Takazawa: Shortest bibranchings and valuated matroid intersection.
    ♦ Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561-573.
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.
30. K. Takazawa: Even factors: Algorithms and structure.
    ♦ Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu, B23 (2010), pp. 233-252.
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)]
33. K. Takazawa: A weighted even factor algorithm.
    ♦ Mathematical Programming, Series A, 115 (2008), pp. 223-237.
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)]

Informal Publications

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

2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.

Theses

• [Ph.D. Thesis] Combinatorial Algorithms for Generalized Matching Problems, University of Tokyo, 2010 (supervised by Kazuo Murota).

• [Master's Thesis] A Unified Approach to Combinatorial Algorithms for Matchings and Matroids, University of Tokyo, 2007 (supervised by Kazuo Murota and Satoru Iwata).