Publications of K. Murota

My technical reports are often included in METR series at Department of Mathematical Engineering of U. Tokyo

• Discrete Convex Analysis
• Valuated Matroid
• Combinatorial Matrix Theory
• Combinatorial Relaxation
• Group-Theoretic Methods in Engineering
• Economic Geography
• Semidefinite Programming
• Numerical Analysis
• Others

• Discrete Convex Analysis

  • Book

    • K. Murota (2003): Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications, Vol.10, Society for Industrial and Applied Mathematics.

  • Tutorial Slides/Videos

    • DC programming in discrete convex analysis [ slide ] at Institute of Mathematics and Applications, February 24, 2015.
    • Discrete DC programming by discrete convex analysis [ slide ] at Mathematics Instutite of Oberwolfach, November 13, 2014.
    • Discrete Convex Analysis: Basics, DC programming, and submodular welfare algorithm [ slide , video ] at NIPS - DISCML workshop, Lake Tahoe, December 9, 2013.
    • Introduction to discrete convex analysis [ slide , video ] at Modern Aspects of Submodularity, Georgia Institute of Technology, March 19-22, 2012.
    • Minimization and maximization algorithms in discrete convex analysis [ slide , video ] at Modern Aspects of Submodularity, Georgia Institute of Technology, March 19-22, 2012.
    • Introduction to discrete convex analysis [ slide ] at Discrete Geometric Analysis, RIMS, Kyoto University, August 30, 2012.
    • M-convex functions on jump systems: A survey [ slide ] at Discrete Convexity and Optimization, RIMS, Kyoto University, October 16, 2012.

    • Discrete convex analysis (slide in Japanese by A. Shioura; July 2, 2010)
    • Auction theory and discrete convex analysis (slide in Japanese by A. Shioura; March 25, 2014)

    Softwares and Demos: DCP (Discrete Convex Paradigm)

  • Surveys

    • K. Murota (1999): Discrete convex analysis -- Exposition on conjugacy and duality, in Graph Theory and Combinatorial Biology (eds. L. Lovasz, A. Gyarfas, G. Katona, A. Recski, L. Szekely) Bolyai Society Mathematical Studies, Vol. 7, 1999, pp. 253-278
    • K. Murota (2000): Algorithms in discrete convex analysis, IEICE Transactions on Systems and Information, E83-D, 344-352.
    • K. Murota (2001): L-convex functions and M-convex functions, Encyclopedia of Optimization, P. M. Pardalos and C. A. Floudas, eds., Kluwer, pp.111-118
    • K. Murota (2009): Recent developments in discrete convex analysis, in: W. Cook, L. Lovasz and J. Vygen, eds., Research Trends in Combinatorial Optimization, Bonn 2008, Springer-Verlag, Berlin, 2009, Chapter 11, 219-260.
    • K. Murota (2015): Discrete convex analysis, Supplemantary material for Summer School (September 21--25, 2015) at Hausdorff Institute of Mathematics, Trimester Program, Combinatorial Optimization

  • Papers

    • K. Murota (1996): Valuated matroid intersection, I: optimality criteria, SIAM Journal on Discrete Mathematics, 9, 545-561.
    • K. Murota (1996): Valuated matroid intersection, II: algorithms. SIAM Journal on Discrete Mathematics, 9, 562-576.
    • K. Murota (1996): Convexity and Steinitz's exchange property, Advances in Mathematics, 124, 272-311.
      • Extended abstract: Integer Programming and Combinatorial Optimization (W. H. Cunningham, S. T. McCormick, and M. Queyranne, eds.), Proceedings of 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 3-5, 1996. Lecture Notes in Computer Science 1084, Springer-Verlag, 1996, pp.260-274.
    • K. Murota (1998): Discrete convex analysis, Mathematical Programming, 83, 313-371.
    • K. Murota (1999): Submodular flow problem with a nonseparable cost function, Combinatorica, 19, 87-109.
    • K. Murota and A. Shioura (1999): M-Convex function on generalized polymatroid, Mathematics of Operations Research, 24, 95-105. [Errata and Supplements]
    • S. Fujishige and K. Murota (2000): Notes on L-/M-convex functions and the separation theorems, Mathematical Programming, 88, 129-146.
    • K. Murota and A. Shioura (2000): Extension of M-convexity and L-convexity to polyhedral convex functions, Advances in Applied Mathematics, 25 (2000), 352-427.
    • K. Murota and A. Shioura (2001): Relationship of M-/L-convex functions with discrete convex functions by Miller and by Favati-Tardella, Discrete Applied Mathematics, 115, 151-176.
    • V. Danilov, G. Koshevoy, and K. Murota (2001): Discrete convexity and equilibria in economies with indivisible goods and money, Mathematical Social Sciences, 41, 251-273
    • S. Moriguchi, K. Murota and A. Shioura (2002): Scaling algorithms for M-convex function minimization, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A, 922-929.
    • K. Murota and A. Shioura (2003): Quasi M-convex and L-convex functions---Quasi-convexity in discrete optimization, Discrete Applied Mathematics, 131/132, 467-494.
    • S. Moriguchi and K. Murota (2003): Capacity scaling algorithm for scalable M-convex submodular flow problems, Optimization Methods and Software, 18, 207-218.
    • K. Murota (2003): On steepest descent algorithms for discrete convex functions, SIAM Journal on Optimization, 14, 699-707.
    • K. Murota and A. Tamura (2003): Application of M-convex submodular flow problem to mathematical economics, Japan Journal of Industrial and Applied Mathematics, 20, 257-277.
      • Twelfth Annual International Symposium on Algorithms and Computation (ISAAC 01), Christchurch, New Zealand, December 19-21, 2001
    • K. Murota and A. Tamura (2003): New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities, Discrete Applied Mathematics, 131, 495-512. Also in the special volume Discrete Applied Mathematics, Editors' Choice, Edition 2003.
    • K. Murota and A. Shioura (2004): Conjugacy relationship between M-convex and L-convex functions in continuous variables, Mathematical Programming, 101, 415-433.
    • K. Murota and A. Tamura (2004): Proximity theorems of discrete convex functions, Mathematical Programming, A99, 539-562.
    • K. Murota and A. Shioura (2004): Fundamental properties of M-convex and L-convex functions in continuous variables, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E87-A, 1042-1052.
    • H. Hirai and K. Murota (2004): M-convex functions and tree metrics, Japan Journal of Industrial and Applied Mathematics, 21, 391-403.
    • K. Murota, H. Saito, and R. Weismantel (2004): Optimality criteria for a class of nonlinear integer programs, Operations Research Letters, 32, 468-472.
    • K. Murota and A. Shioura (2005): Substitutes and complements in network flows viewed as discrete convexity, Discrete Optimization, 2, 256-268.
    • S. Moriguchi and K. Murota (2005): Discrete Hessian matrix for L-convex functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E88-A, 1104-1108.
    • S. Iwata, S. Moriguchi and K. Murota (2005): A capacity scaling algorithm for M-convex submodular flow, Mathematical Programming, 103, 181-202.
    • K. Murota (2005): Note on multimodularity and L-convexity, Mathematics of Operations Research, 30, 658-661.
    • T. Iimura, K. Murota and A. Tamura (2005): Discrete fixed point theorem reconsidered, Journal of Mathematical Economics, 41, 1030-1036.
    • K. Murota (2006): M-convex functions on jump systems: A general framework for minsquare graph factor problem, SIAM Journal on Discrete Mathematics, 20, 213-226.
    • K. Murota and K. Tanaka (2006): A steepest descent algorithm for M-convex functions on jump systems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A, 1160-1165.
    • Y. Kobayashi, K. Murota and K. Tanaka (2007): Operations on M-convex functions on jump systems, SIAM Journal on Discrete Mathematics, 21, 107-129.
    • Y. Kobayashi and K. Murota (2007): Induction of M-convex functions by linking systems, Discrete Applied Mathematics, 155, 1471-1480.
    • K. Murota and A. Shioura (2008): Note on the continuity of M-convex and L-convex functions in continuous variables, Journal of the Operations Research Society of Japan, 51, 265-273.
    • K. Murota (2010): Submodular function minimization and maximization in discrete convex analysis, RIMS Kokyuroku Bessatsu, B23, 193-211.
    • Y. Kobayashi, K. Murota and R. Weismantel (2012): Cone superadditivity of discrete convex functions, Mathematical Programming, Series A, 135, 25-44.
    • S. Moriguchi and K. Murota (2012): On discrete Hessian matrix and convex extensibility, Journal of the Operations Research Society of Japan, 55, 48-62.
    • T. Iimura, K. Murota and A. Tamura (2012): Sperner's lemma and zero point theorems on a discrete simplex and a discrete simplotope, Discrete Applied Mathematics, 160, 588-592.
    • K. Murota, A. Shioura and Z. Yang (2013): Computing a Walrasian equilibrium in iterative auctions with multiple differentiated items, METR 2013-10, Department of Mathematical Informatics, University of Tokyo. Revised version (September 2013) .
    • K. Murota and A. Shioura (2014): Dijkstra's algorithm and L-concave function maximization, Mathematical Programming, Series A, 145, 163-177.
    • K. Murota and A. Shioura (2014): Exact bounds for steepest descent algorithms of L-convex function minimization, Operations Research Letters, 42, 361-366.
    • K. Murota and Y. Yokoi (2015): On the lattice structure of stable allocations in two-sided discrete-concave market, Mathematics of Operations Research, 40, 460-473.
    • T. Maehara and K. Murota (2015): A framework of discrete DC programming by discrete convex analysis, Mathematical Programming, Series A, 152, 435-466.
    • S. Fujishige, K. Murota and A. Shioura (2015): Monotonicity in steepest ascent algorithms for polyhedral L-concave functions, Journal of the Operations Research Society of Japan, 58, 184-208.
    • K. Murota (2015): On polyhedral approximation of L-convex and M-convex functions, Journal of the Operations Research Society of Japan,, Vol. 58, No.4, to appear.

  • Technical Notes

    • A proof of the M-convex intersection theorem (January 2004)
    • On infimal convolution of M-convex functions (March 2004)
    • A proof of the L-optimality criterion theorem (July 2004)

  • Books and Expositions in Japanese

    • 室田一雄 (1998): 離散凸解析. 「離散構造とアルゴリズムV」 (藤重悟 編)，近代科学社, 第2章, 51-100.
    • 室田一雄 (2001): 「離散凸解析」， 共立出版.
    • 室田一雄 (2007): 「離散凸解析の考えかた---最適化における離散と連続の数理」， 共立出版.
    • 室田一雄，塩浦 昭義 (2013): 「離散凸解析と最適化アルゴリズム」， 朝倉書店.

    • Expository article for JSIAM (in Japanese, 1996)
    • Expository article for JORSJ (in Japanese, 1997)
    • Expository article for RIMS (in Japanese, 2004)
    • Expository article for Japan. Math. Society (in Japanese, 2004)

• Valuated Matroid

  • Books

    • K. Murota (2000): Matrices and Matroids for Systems Analysis. Algorithms and Combinatorics, Vol.20, Springer-Verlag; paperback 2010. (Chapter 5)

  • Papers

    • K. Murota (1995): Finding optimal minors of valuated bimatroids, Appl. Math. Letters, 8, 37-42.
    • K. Murota (1996): Two algorithms for valuated delta-matroids Appl. Math. Letters, 9, 67-71.
    • K. Murota (1996): Valuated matroid intersection, I: optimality criteria, SIAM Journal on Discrete Mathematics, 9, 545-561.
    • K. Murota (1996): Valuated matroid intersection, II: algorithms. SIAM Journal on Discrete Mathematics, 9, 562-576.
    • K. Murota (1996): On exchange axioms for valuated matroids and valuated delta-matroids, Combinatorica, 6, 591-596.
    • K. Murota (1997): Matroid valuation on independent sets, J. Combinatorial Theory, B69, 59-78.
    • K. Murota (1997): Characterizing a valuated delta-matroid as a family of delta-matroids, J. Operations Research Society of Japan, 40, 565-578.
    • K. Murota (1998): Fenchel-type duality for matroid valuations, Mathematical Programming, 82, 357-375.
      • Original full version: Bonn report, OR95841, 1995.
    • K. Murota (1999): On the degree of mixed polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 20, 196-227.
    • K. Murota and A. Tamura (2001): On circuit valuation of matroids, Advances in Applied Mathematics, 26, 192-225.
    • T. Maehara and K. Murota (2015): Valuated matroid-based algorithm for submodular welfare problem, Annals of Operations Research, 229, 565-590.

• Combinatorial Matrix Theory

  • Books

    • K. Murota (1987): Systems Analysis by Graphs and Matroids - Structural Solvability and Controllability. Algorithms and Combinatorics, Vol.3, Springer-Verlag.
    • K. Murota (2000): Matrices and Matroids for Systems Analysis. Algorithms and Combinatorics, Vol.20, Springer-Verlag; paperback 2010.

  • Tutorial Slides

    • Concept of mixed matrices (in Japanese) [ slide ] at Aihara Project, 1st Hybrid System Workshop, University of Tokyo, November 17-18, 2008.

    Softwares and Demos (CCF-decomposition of LM-matrix)

  • Surveys

    • K. Murota (1993): Mixed matrices - Irreducibility and decomposition. Combinatorial and Graph-Theoretic Problems in Linear Algebra (R. A. Brualdi, S. Friedland and V. Klee, eds.) The IMA Volumes in Mathematics and Its Applications, Vol. 50, Springer, 39 - 71.
    • K. Murota (1996): Structural approach in systems analysis by mixed matrices -- An exposition for index of DAE, ICIAM 95 (Proceedings of the Third International Congress on Industrial and Applied Mathematics held in Hamburg, Germany, July 3-7, 1995) Klaus Kirchgaessner, Osker Mahrenholtz, and Reinhard Mennicken, eds., Mathematical Research, Vol. 87, Akademie Verlag, pp. 257-279.

  • Papers

    • K. Murota (1983): LU-decomposition of a matrix with entries of different kinds, Linear Algebra and Its Applications, 49, 275-283.
    • K. Murota and M. Iri (1985): Structural solvability of systems of equations---A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems, Japan Journal of Applied Mathematics, 2, 247-271.
    • K. Murota (1985): Use of the concept of physical dimensions in the structural approach to systems analysis, Japan Journal of Applied Mathematics, 2, 471-494.
    • K. Murota (1987): Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations, Discrete Applied Mathematics, 17, 107-134.
    • K. Murota, M. Iri and M. Nakamura (1987): Combinatorial canonical form of layered mixed matrices and its application to block-triangularization of systems of equations, SIAM Journal on Algebraic and Discrete Methods, 8, 123-149.
    • K. Murota (1987): Refined study on structural controllability of descriptor systems by means of matroids, SIAM Journal on Control and Optimization, 25, 967-989.
    • K. Murota (1989): On the irreducibility of layered mixed matrices, Linear and Multilinear Algebra, 24 (1989), 273-288.
    • K. Murota (1989): Some recent results in combinatorial approaches to dynamical systems, Linear Algebra and Its Applications, 122/123/124, 725-759
    • K. Murota (1989/90): Combinatorial dynamical system theory - General framework and controllability criteria, Discrete Applied Mathematics, 22, 241-265.
    • K. Murota (1989): A matroid-theoretic approach to structurally fixed modes of control systems, SIAM Journal on Control and Optimization, 27, 1381-1402.
    • K. Murota (1990): Eigensets and power products of a bimatroid, Advances in Mathematics, 80, 78-91.
    • K. Murota (1990): Principal structure of layered mixed matrix, Discrete Applied Mathematics, 27, 221-234.
    • K. Murota and S. Poljak (1990): Note on a graph-theoretic criterion for structural output controllability, IEEE Transactions on Automatic Control, 35, 939-942.
    • K. Murota and J. van der Woude (1991): Structure at infinity of structured descriptor systems and its applications, SIAM Journal on Control and Optimization, 29, 878-894.
    • K. Murota (1991): On the Smith normal form of structured polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 12, 747-765.
    • K. Murota (1993): Hierarchical decomposition of symmetric discrete systems by matroid and group theories, Mathematical Programming, Series A, 59, 377-404.
    • K. Murota (1993): On the Smith normal form of structured polynomial matrices II, SIAM Journal on Matrix Analysis and Applications, 14, 1103-1111.
    • H. Ito, S. Iwata and K. Murota (1994): Block-triangularization of partitioned matrices under similarity/equivalence transformations, SIAM Journal on Matrix Analysis and Applications, 15, 1226-1255.
    • S. Iwata and K. Murota (1995): A theorem on the principal structure for independent matchings, Discrete Applied Mathematics, 61, 229-244.
    • S. Iwata and K. Murota (1995): A minimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices, SIAM J. Matrix Analy. Appl., 16, 719-734.
    • S. Iwata and K. Murota (1996): Horizontal principal structure of layered mixed matrices --- Decomposition of discrete systems by design-variable selections, SIAM J. Disc. Math., 9, 71-86.
    • K. Murota and M. Scharbrodt (1998): Computing the combinatorial canonical form of a layered mixed matrix, Optimization and Mathematical Software, 10, 373-391.
    • K. Murota (1999): On the degree of mixed polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 20, 196-227.
    • J. Geelen, S. Iwata, and K. Murota (2003): The linear delta-matroid parity problem, J. Combinatorial Theory, B88, 377-398.
    • K. Murota (2012): Legendre duality in combinatorial study of matrix pencils, Japan Journal of Industrial and Applied Mathematics, 29, 205-236.

  • Expositions in Japanese

    • 室田一雄 (1991): 離散システムの不変な階層構造を求めて --- グラフからマトロイドへ, 応用数理，1, 230-248. (Hierarchical decompositions of discrete systems --- exploiting invariant structure by matroid; Bulletin of the Japan Society for Industrial and Applied Mathematics, 1, 230-248).
    • 室田一雄 (1992): マトロイドとシステム解析. 「離散構造とアルゴリズムI」 (藤重悟 編)，近代科学社, 第2章, 57-109.
    • 室田一雄 (2002): 数理工学への誘い： 混合行列の話 (東京大学工学部計数工学科数理情報工学コース編), 日本評論社, 第13章, 139-149.

• Combinatorial Relaxation

  • Books

    • K. Murota (2000): Matrices and Matroids for Systems Analysis. Algorithms and Combinatorics, Vol.20, Springer-Verlag; paperback 2010. (Chapter 7)

  • Papers

    • K. Murota (1990): Computing Puiseux-series solutions to determinantal equations via combinatorial relaxation, SIAM Journal on Computing, 19, 1132-1161.
    • K. Murota (1995): Computing the degree of determinants via combinatorial relaxation, SIAM Journal on Computing, 24, 765-796.
    • K. Murota (1995): Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form. Applicable Algebra in Engineering, Communication and Computing, 6, 251-273.
    • K. Murota (1995): An identity for matching and skew-symmetric determinant, Linear Algebra and Its Applications, 218, 1-27.
    • K. Murota (1995): An identity for bipartite matching and symmetric determinant, Linear Algebra and Its Applications, 222, 261-274.
    • S. Iwata, K. Murota and I. Sakuta (1996): Primal-dual combinatorial relaxation algorithms for the maximum degree of subdeterminants, SIAM J. Scientific Computing, 17, 993-1012.
    • S. Iwata and K. Murota (2001): Combinatorial relaxation algorithm for mixed polynomial matrices, Mathematical Programming, Series A, 90, 353-371.

• Group-Theoretic Methods in Engineering

  • Books

    • K. Ikeda and K. Murota (2002): Imperfect Bifurcation in Structures and Materials: Engineering Use of Group-Theoretic Bifurcation Theory, 1st ed., Springer-Verlag.
    • K. Ikeda and K. Murota (2010): Imperfect Bifurcation in Structures and Materials: Engineering Use of Group-Theoretic Bifurcation Theory, 2nd ed., Springer-Verlag.

  • Tutorial Slides

    • Recent progress in simultaneous block-diagonalization methods (with T. Maehara) (in Japanese) at RIMS, Kyoto University, October 24, 2012.

  • Softwares

    • MM algorithm for simultaneous block-diagonalization of matrices (by T. Maehara)

  • Papers

    • K. Murota and K. Ikeda (1991): Computational use of group theory in bifurcation analysis of symmetric structures, SIAM Journal on Scientific and Statistical Computing, 12, 273-297.
    • K. Murota and K. Ikeda (1991): Critical imperfection of symmetric structures. SIAM Journal on Applied Mathematics, 51, 1222-1254.
    • K. Ikeda and K. Murota (1991): Bifurcation analysis of symmetric structures using block-diagonalization, Computer Methods in Applied Mechanics and Engineering, 86, 215-243.
    • K. Murota and K. Ikeda (1992): On random imperfections for structures of regular-polygonal symmetry, SIAM Journal on Applied Mathematics, 52, 1780-1803.
    • K. Ikeda and K. Murota (1993): Statistics of normally distributed random initial imperfections. International Journal of Solids and Structures, 30, 2445-2467.
    • K. Murota (1993): Hierarchical decomposition of symmetric discrete systems by matroid and group theories, Mathematical Programming, Series A, 59, 377-404.
    • K. Ikeda, K. Murota and M. Nakano (1994): Echelon modes in uniform materials. International Journal of Solids and Structures, 31, 2709-2733.
    • K. Ikeda and K. Murota (1997): Recursive bifurcation as sources of complexity in soil shearing behavior, Soils and Foundations, 37, 17-29.
    • K. Ikeda, K. Murota, Y. Yamakawa, and E. Yanagisawa (1997): Mode switching and recursive bifurcation in granular materials, Journal of the Mechanics and Physics of Solids, 45, No. 11/12, 1929-1953.
    • K. Ikeda and K. Murota (1999): Systematic description of imperfect bifurcation behavior of symmetric systems, International Journal of Solids and Structures, 36, No. 11, 1561-1596.
    • K. Murota, K. Ikeda and K. Terada (1999): Bifurcation mechanism underlying echelon-mode formation, Computer Methods in Applied Mechanics and Engineering, 170, 423-448.
    • R. Tanaka and K. Murota (1999): Fault-tolerance of control systems with dihedral group symmetry, Trans. Soc. Instr. Control Engin., 35, 806-813.
    • R. Tanaka and K. Murota (2000): Quantitative analysis for controllability of symmetric control systems, International Journal of Control, 73, 254-264.
    • R. Tanaka and K. Murota (2000): Symmetric failures in symmetric control systems, Linear Algebra and Its Applications, 318, 145-172.
    • Y. Kanno, M. Ohsaki, K. Murota, and N. Katoh (2001): Group symmetry in interior-point methods for semidefinite program, Optimization and Engineering, 2, 293-320.
    • I. Saiki, K. Ikeda and K. Murota (2005): Flower patterns appearing on a honeycomb structure and their bifurcation mechanism, International Journal of Bifurcation and Chaos, 56, 497-515.
    • K. Ikeda, K. Murota, A. Yanagimoto and H. Noguchi (2007): Improvement of the scaled corrector method for bifurcation analysis using symmetry-exploiting block-diagonalization, Computer Methods in Applied Mechanics and Engineering, 196, 1648-1661.
    • K. Ikeda, Y. Yamakawa, J. Desrues and K. Murota (2008): Bifurcations to diversify geometrical patterns of shear bands on granular material, Physical Review Letters, Vol.100, No.19, 2008, 198001 (1-4).
    • K. Murota, Y. Kanno, M. Kojima and S. Kojima (2010): A numerical algorithm for block-diagonal decomposition of matrix *-algebras with application to semidefinite programming, Japan Journal of Industrial and Applied Mathematics, 27, 125-160.
    • T. Maehara and K. Murota (2010): A numerical algorithm for block-diagonal decomposition of matrix *-algebras with general irreducible components, Japan Journal of Industrial and Applied Mathematics, 27, 263-293.
    • T. Maehara and K. Murota (2010): Error controlling algorithm for simultaneous block-diagonalization and its application to independent component analysis, JSIAM Letters, 2, 131-134.
    • T. Maehara and K. Murota (2011): Simultaneous singular value decomposition, Linear Algebra and Its Applications, 435, 106-116.
    • T. Maehara and K. Murota (2011): Algorithm for error-controlled simultaneous block-diagonalization of matrices, SIAM Journal on Matrix Analysis and Applications, 32, 605-620.
    • D. Aiura, N. Kakimura, and K. Murota (2013): On the number of matrices to generate a matrix *-algebra over the real field, Linear Algebra and Its Applications, 438, 1252-1266.

• Economic Geography

  • Books

    • K. Ikeda and K. Murota (2014): Bifurcation Theory for Hexagonal Agglomeration in Economic Geography, Springer-Verlag.

  • Tutorial Slides

    • Bifurcation theory for hexagonal agglomeration in economic geography at Institute of Economic Research, Kyoto University, March 20, 2014.

  • Papers

    • K. Ikeda, K. Murota, T. Akamatsu, T. Kono, Y. Takayama (2011): Self-organizing hexagons for core-periphery models: Central place theory and group theory, METR 2011-24, Department of Mathematical Informatics, University of Tokyo.
    • K. Ikeda, K. Murota, and T. Akamatsu (2012): Self-organization of Losch's hexagons in economic agglomeration for core-periphery models, International Journal of Bifurcation and Chaos, Vol. 22 (2012), No.8, 1230026 (29 pages; 1230026-1 to 1230026-29). Erratum
    • K. Ikeda, K. Murota, T. Akamatsu, T. Kono, and Y. Takayama (2014): Self-organization of hexagonal agglomeration patterns in new economic geography models, Journal of Economic Behavior & Organization, 99, 32-52

• Semidefinite Programming

  • Papers

    • M. Fukuda, M. Kojima, K. Murota, and K. Nakata (2000): Exploiting sparsity in semidefinite programming via matrix completion, I: General framework SIAM J. Optimization, 11, 647-674
    • Y. Kanno, M. Ohsaki, K. Murota, and N. Katoh (2001): Group symmetry in interior-point methods for semidefinite program, Optimization and Engineering, 2, 293-320
    • K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima and K. Murota (2003): Exploiting sparsity in semidefinite programming via matrix completion, II: Implementation and numerical results, Mathematical Programming, B95, 303-327.
    • K. Murota, Y. Kanno, M. Kojima and S. Kojima (2010): A numerical algorithm for block-diagonal decomposition of matrix *-algebras with application to semidefinite programming, Japan Journal of Industrial and Applied Mathematics, 27, 125-160.

• Numerical Analysis

  • Books in Japanese

    • M. Sugihara and K. Murota (1994): Elements of Numerical Computations, Iwanami (in Japanese)
      [杉原正顯，室田一雄 (1994): 数値計算法の数理. 岩波書店]
    • M. Sugihara and K. Murota (2009): Theoretical Numerical Linear Algebra, Iwanami (in Japanese)
      [杉原正顯, 室田一雄 (2009): 線形計算の数理. 岩波書店]

  • Papers

    • 室田一雄 (1980)： 平野の変形Newton法の大域的収束性, 情報処理学会論文誌，21, 469-474.
    • K. Murota (1982): Global convergence of a modified Newton iteration for algebraic equations. SIAM Journal on Numerical Analysis, 19, 793-799.
    • K. Murota and M. Iri (1982): Parameter tuning and repeated application of the IMT-type transformation in numerical quadrature, Numerische Mathematik, 38, 347-363.
    • M. Sugihara and K. Murota (1982): A note on Haselgrove's method for numerical integration, Mathematics of Computation, 39, 549-554.
    • 室田一雄 (1993)： 代用電荷法におけるスキームの「不変性」について． 情報処理学会論文誌，34, 533-535.
    • K. Murota (1993): On "invariance" of schemes in the fundamental solutions method, Trans. Information Processing Society of Japan, 34, 533-535.
    • K. Tanaka, M. Sugihara, and K. Murota (2004): Numerical indefinite integration by double exponential sinc method, Mathematics of Computation, 74, 655-679.
    • 相島 健助，松尾 宇泰，室田 一雄，杉原 正顯 (2007)： 特異値計算のための dqds 法と mdLVs 法の収束性について． 日本応用数理学会論文誌，第17巻，97-131.
    • K. Tanaka, M. Sugihara, and K. Murota (2008): Complex-analytic approach to the Sinc-Gauss sampling formula, Japan Journal of Industrial and Applied Mathematics, Vol. 25 (2008), No. 2, 209-231.
    • K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2008): On convergence of the dqds algorithm for singular value computation, SIAM Journal on Matrix Analysis and Applications, 30, 522-537.
    • K. Aishima, T. Matsuo and K. Murota (2008): Rigorous proof of cubic convergence of the dqds algorithm for singular values, Japan Journal of Industrial and Applied Mathematics, 25 (2008), 65-81.
    • K. Tanaka, M. Sugihara, and K. Murota (2009): Function classes for successful DE-Sinc approximations, Mathematics of Computation, Vol.78 (2009), pp.1553-1571.
    • K. Tanaka, M. Sugihara, K. Murota, and M. Mori (2009): Function classes for double exponential integration formulas, Numerische Mathematik, 111, 631-655.
    • K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2010): Superquadratic convergence of DLASQ for computing matrix singular values, Journal of Computational and Applied Mathematics, 234, 1179-1187
    • K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2010): A survey on convergence theorems of the dqds algorithm for computing singular values, Journal of Math-for-Industry, 2 (2010A-1), 1-11.
    • K. Aishima, T. Matsuo and K. Murota (2011): A note on the dqds algorithm with Rutishauser's shift for singular values, Japan Journal of Industrial and Applied Mathematics, 28, 251-262.
    • K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2012): A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence, Journal of Computational and Applied Mathematics, 236, 3556-3560.
    • K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2014): A shift strategy for superquadratic convergence in the dqds algorithm for singular values, Journal of Computational and Applied Mathematics, 257, 132-143.

• Others

  • Statistics

    • K. Murota and K. Takeuchi (1981): The studentized empirical characteristic function and its application to test for the shape of distribution, Biometrika, 68, 55-65.

  • Voronoi Diagram

    • T. Ohya, M. Iri and K. Murota (1984): A fast Voronoi-diagram algorithm with quaternary tree bucketing, Information Processing Letters, 18, 227-231.
    • M. Iri, K. Murota and T. Ohya (1984): A fast Voronoi-diagram algorithm with applications to geographical optimization problems, In System Modelling and Optimization (P. Thoft-Christensen, ed.) Lecture Notes in Control and Information Sciences, 59, Springer, 1984, 273-288.
    • T. Ohya, M. Iri and K. Murota (1984): Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms, Journal of the Operations Research Society of Japan, 27, 306-337.
    • H. Imai, M. Iri and K. Murota (1985): Voronoi diagram in the Laguerre geometry and its applications, SIAM Journal on Computing, 14, 93-105.
    • T. Asano, M. Edahiro, H. Imai, M. Iri and K. Murota (1985): Practical use of bucketing techniques in computational geometry, Computational Geometry, G. T. Toussaint ed., North-Holland, 1985, 153-195.
    • M. Iri, K. Kubota and K. Murota (1991): Geometrical/geographical optimization and fast automatic differentiation, Yugoslav Journal of the Operations Research, 1, 121-134.

  • Graph, Newtork, Matroid, Discrete Optimization

    • M. Iri, K. Murota and S. Matsui (1981): Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane, Information Processing Letters, 12, 206-209.
    • M. Iri, K. Murota and S. Matsui (1982): An approximate solution for the problem of optimizing the plotter pen movement, In System Modelling and Optimization (R.F.Drenick and F. Kozin, eds.) Lecture Notes in Control and Information Sciences, 38, Springer, 1982, pp. 572-580.
    • M. Iri, K. Murota and S. Matsui (1983): Heuristics for planar minimum-weight perfect matchings, Networks, 13, 67-92.
    • K. Murota (1987): Homotopy base of acyclic graphs---A combinatorial analysis of commutative diagrams by means of preordered matroid, Discrete Applied Mathematics, 17, 135-155.
    • K. Murota and S. Fujishige (1987): Finding a homotopy base for directed paths in an acyclic graph, Discrete Applied Mathematics, 17, 157-162.
    • K. Murota (1988): Note on the universal bases of a pair of polymatroids, Journal of the Operations Research Society of Japan, 31, 565-572.
    • S. Iwata, K. Murota and M. Shigeno (1997): A fast submodular intersection algorithm for strong map sequences, Mathematics of Operations Research, 22, 803-813.
    • T. Suzuki. S. Aoki and K. Murota (2005): Use of primal-dual technique in the network algorithm for two-way contingency tables, Japan Journal of Industrial and Applied Mathematics, 22, 133-145.
    • H. Hirai, K. Murota, and M. Rikitoku (2005): SVM kernel by electric network, Pacific Journal of Optimization, 1, 509-526.
    • H. Saito and K. Murota (2007): Benders decomposition approach to robust mixed integer programming, Pacific Journal of Optimization, 3, 99-112.
    • H. Hirai, K. Murota, and M. Rikitoku (2007): Electric network classifiers for semi-supervised learning on graphs, Journal of the Operations Research Society of Japan, 50, 218-231.
    • K. Otsuki, Y. Kobayashi, and K. Murota (2015): Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network, European Journal of Operational Research, to appear.