Selected publications of K. Murota

Publications of K. Murota

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

Books

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

Softwares and Demos: DCP (Discrete Convex Paradigm)

Tutorial Slides/Videos

Extensions and ramifications of discrete convexity concepts [ slide ] at Hausdorff Institute of Mathematics, Bonn, Trimester Program, Combinatorial Optimization, October 6, 2015.
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.

Summer School (Hausdorff Institute of Mathematics, Bonn, May, 2016)

Part I: Concepts of discrete convex functions
Part II: Properties of discrete convex functions
Part III: Algorithms for discrete convex functions

Summer School (Hausdorff Institute of Mathematics, Bonn, September, 2015)

Abstract
Part 1 (Convex Analysis View on Combinatorial Optimization) [ video ]
Part 2 (Properties of L-convex and M-convex Functions) [ video ]
Part 3 (Conjugacy and Duality Theorems and Their Implications) [ video ]

Discrete convex analysis (slide in Japanese by A. Shioura; July 2, 2010)

Other Slides

Discrete convex analysis view on discrete decreasing minimization [ slide ] at The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, May 28, 2019.
DC programming in discrete convex analysis [ slide ] at The 6th Asian Conference on Nonlinear Analysis and Optimization, November 7, 2018.
DC programming in discrete convex analysis [ slide ] at Institute of Mathematics and Applications, February 24, 2015.
M-convex functions on jump systems: A survey [ slide ] at Discrete Convexity and Optimization, RIMS, Kyoto University, October 16, 2012.

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

Survey Papers

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, 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
K. Murota (2016): Discrete convex analysis: A tool for economics and game theory, Journal of Mechanism and Institution Design, Vol.1 (2016), No.1, 151-273. (Revised version available at http://arxiv.org/abs/2212.03598)
K. Murota (2021): A survey of fundamental operations on discrete convex functions of various kinds, Optimization Methods and Software, Vol.36 (2021), Nos.2-3, 472-518.
K. Murota (2021): On basic operations related to network induction of discrete convex functions, Vol.36 (2021), Nos.2-3, 519-559.
S. Moriguchi and K. Murota (2023): Inclusion and intersection relations between fundamental classes of discrete convex functions. Journal of the Operations Research Society of Japan, Vol.66 (2023), No.3, 187-217.
K. Murota and A. Tamura (2023): Recent progress on integrally convex functions. Japan Journal of Industrial and Applied Mathematics, Vol. 40 (2023), No.3, 1445-1499.
https://doi.org/10.1007/s13160-023-00589-4 (Open access)

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]
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
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 (2000): Algorithms in discrete convex analysis, IEICE Transactions on Systems and Information, E83-D, 344-352.
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 (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 (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, The 24th International Symposium on Algorithms and Computation (ISAAC 2013), L. Cai, S.-W. Cheng, and T.-W. Lam (Eds.): ISAAC2013, Lecture Note in Computer Science 8283, 468-478, 2013. Detailed version: METR 2013-10, June 2013 (revised 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, 58, 291-305.
K. Murota, A. Shioura, and Z. Yang (2016): Time bounds for iterative auctions: A unified approach by discrete convex analysis, Discrete Optimization, 19, 36-62. [Errata]
K. Murota (2016): Discrete convex analysis: A tool for economics and game theory, Journal of Mechanism and Institution Design, Vol.1 (2016), No.1, 151-273. (Revised version available at http://arxiv.org/abs/2212.03598)
K. Murota and A. Shioura (2017): Note on time bounds of two-phase algorithms for L-convex function minimization, Japan Journal of Industrial and Applied Mathematics, Vol. 34 (2017), pp.429-440.
T. Maehara, N. Marumo, and K. Murota (2018): Continuous relaxation for discrete DC programming, Mathematical Programming, Series B, Vol.169 (2018), pp.199-219. DOI 10.1007/s10107-017-1139-2
K. Murota (2018): Multiple exchange property for M#-concave functions and valuated matroids, Mathematics of Operations Research, Vol. 43 (2018) pp. 781-788.
Y. Iwamasa, K. Murota, and S. Zivny (2018): Discrete convexity in joint winner property, Discrete Optimization, Vol.28 (2018), pp.78-88.
K. Murota and A. Shioura (2018): Simpler exchange axioms for M-concave functions on generalized polymatroids, Japan Journal of Industrial and Applied Mathematics, Vol.35 (2018), No.1, pp.235-259.
K. Murota (2018): A stronger multiple exchange property for M#-concave functions, Japan Journal of Industrial and Applied Mathematics, Vol.35 (2018), No.1, pp. 411-421.
K. Murota and A. Shioura (2018): On equivalence of M#-concavity of a set function and submodularity of its conjugate, Journal of the Operations Research Society of Japan, Vol.61 (2018), No.2, pp.163-171.
H. Hirai, Y. Iwamasa, K. Murota, and S. Zivny (2018): Beyond JWP: A tractable class of binary VCSPs via M-convex intersection, Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen (France), 2018.
H. Hirai, Y. Iwamasa, K. Murota, and S. Zivny (2019): A tractable class of binary VCSPs via M-convex intersection, ACM Transactions on Algorithms, Vol.15, No.3, Article 44 (July 2019), 41 pages. https://doi.org/10.1145/3329862
M. Bolandnazar, W. T. Huh, S. T. McCormick, and K. Murota (2019): Error noted in "Order-Based Cost Optimization in Assemble-to-Order Systems" by Lu and Song (2005), Operations Research, Vol. 67, No.1 (2019), pp.163-166. https://doi.org/10.1287/opre.2018.1789
S. Moriguchi and K. Murota (2019): Projection and convolution operations for integrally convex functions, Discrete Applied Mathematics, Vol.255 (2019), 283-298.
S. Moriguchi and K. Murota (2019): On fundamental operations for multimodular functions, Journal of the Operations Research Society of Japan, Vol.62 (2019), No.2, 53-63. [Errata]
S. Moriguchi, K. Murota, A. Tamura, and F. Tardella (2019): Scaling, proximity, and optimization of integrally convex functions, Mathematical Programming, Vol.175 (2019), 119-154.
S. Moriguchi, K. Murota, A. Tamura, and F. Tardella (2020): Discrete midpoint convexity, Mathematics of Operations Research, Vol. 45 (2020), 99-128. https://doi.org/10.1287/moor.2018.0984
K. Murota and A. Tamura (2020): Integrality of subgradients and biconjugates of integrally convex functions, Optimization Letters, Vol.14 (2020), 195-208. https://link.springer.com/article/10.1007/s11590-019-01501-1
K. Murota (2021): A survey of fundamental operations on discrete convex functions of various kinds, Optimization Methods and Software, Vol.36 (2021), Nos.2-3, 472-518.
K. Murota (2021): On basic operations related to network induction of discrete convex functions, Vol.36 (2021), Nos.2-3, 519-559.
K. Murota and K. Takazawa (2021): Relationship of two formulations for shortest bibranchings, Japan Journal of Industrial and Applied Mathematics, Vol.38 (2021), No.1, pp.141-161. https://doi.org/10.1007/s13160-020-00432-0
K. Murota (2021): A note on M-convex functions on jump systems, Discrete Applied Mathematics, Vol.289 (2021), 492-502.
A. Frank and K. Murota (2018+): Discrete decreasing minimization, Part II: Views from discrete convex analysis, arXiv: http://arxiv.org/abs/1808.08477
A. Frank and K. Murota (2022): A discrete convex min-max formula for box-TDI polyhedra, Mathematics of Operations Research, Vol.47 (2022), No.2, 1026-1047. Published on-line (October 18,2021) https://doi.org/10.1287/moor.2021.1160 arXiv: http://arxiv.org/abs/2007.03507
A. Frank and K. Murota (2022): Decreasing minimization on M-convex sets: Background and structures, Mathematical Programming, Vol.195 (2022), No.1-2, 977-1025.
https://doi.org/10.1007/s10107-021-01722-2 SharedIt link: https://rdcu.be/cAj1K arXiv: http://arxiv.org/abs/2007.09616
A. Frank and K. Murota (2022): Decreasing minimization on M-convex sets: Algorithms and applications, Mathematical Programming, Vol.195 (2022), No.1-2, 1027-1068.
https://doi.org/10.1007/s10107-021-01711-5 SharedIt link: https://rdcu.be/czA6n arXiv: http://arxiv.org/abs/2007.09618
K. Murota and A. Tamura (2022): Discrete Fenchel duality for a pair of integrally convex and separable convex functions, Japan Journal of Industrial and Applied Mathematics, Vol.39 (2022), No.2, 599-630. https://doi.org/10.1007/s13160-022-00499-x (Open access)
A. Frank and K. Murota (2022): Fair integral submodular flows, Discrete Applied Mathematics, Vol.320 (2022), 416-434. https://doi.org/10.1016/j.dam.2022.06.015
A. Frank and K. Murota (2023): Fair integral flows. Mathematics of Operations Research, Vol.48 (2023), No.3, 1393-1422. https://doi.org/10.1287/moor.2022.1303
A. Frank and K. Murota (2023): Decreasing minimization on base-polyhedra: Relation between discrete and continuous cases, Japan Journal of Industrial and Applied Mathematics, Vol.40 (2023), No.1, 183-221.
https://link.springer.com/article/10.1007/s13160-022-00511-4 , SharedIt link: https://rdcu.be/cPlmC
S. Moriguchi and K. Murota (2023): Note on the polyhedral description of the Minkowski sum of two L-convex sets. Japan Journal of Industrial and Applied Mathematics, Vol.40 (2023), No.1, 223-263.
https://doi.org/10.1007/s13160-022-00512-3 (Open access)
S. Moriguchi and K. Murota (2023): Inclusion and intersection relations between fundamental classes of discrete convex functions. Journal of the Operations Research Society of Japan, Vol.66 (2023), No.3, 187-217.
K. Murota and A. Tamura (2023): Recent progress on integrally convex functions. Japan Journal of Industrial and Applied Mathematics, Vol. 40 (2023), No.3, 1445-1499.
https://doi.org/10.1007/s13160-023-00589-4 (Open access)
K. Murota and A. Tamura (2023): Shapley-Folkman-type theorem for integrally convex sets. arXiv: http://arxiv.org/abs/2305.15125
K. Murota and A. Shioura (2023): Note on minimization of quasi M-natural-convex functions. Japan Journal of Industrial and Applied Mathematics, Published online: December 8, 2023
https://doi.org/10.1007/s13160-023-00633-3 (Open access)
K. Murota and A. Tamura (2023): Decomposition of an integrally convex set into a Minkowski sum of bounded and conic integrally convex sets. arXiv: http://arxiv.org/abs/2306.09072
K. Murota and A. Tamura (2023): Note on Minkowski summation and unimodularity in discrete convex analysis. arXiv: http://arxiv.org/abs/2312.01822

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)
Proof of biconjugacy of univariate discrete convex functions (November 2021)

Books and Expositions in Japanese

��c��Y (1998): ��U�ʉ��. �u��U�\��ƃA��S��Y��V�v (��d�� )�C�ߑ�Ȋw��, ��2��, 51-100.
��c��Y (2001): �u��U�ʉ�́v�C ��o��.
��c��Y (2007): �u��U�ʉ�͂̍l��---�œK��ɂ��闣�U�ƘA��̐��v�C ��o��.
��c��Y�C��Y ��` (2013): �u��U�ʉ�͂ƍœK��A��S��Y��v�C ��q��X.

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
  1. K. Murota (1995): Finding optimal minors of valuated bimatroids, Appl. Math. Letters, 8, 37-42.
  2. K. Murota (1996): Two algorithms for valuated delta-matroids Appl. Math. Letters, 9, 67-71.
  3. K. Murota (1996): Valuated matroid intersection, I: optimality criteria, SIAM Journal on Discrete Mathematics, 9, 545-561.
  4. K. Murota (1996): Valuated matroid intersection, II: algorithms. SIAM Journal on Discrete Mathematics, 9, 562-576.
  5. K. Murota (1996): On exchange axioms for valuated matroids and valuated delta-matroids, Combinatorica, 6, 591-596.
  6. K. Murota (1997): Matroid valuation on independent sets, J. Combinatorial Theory, B69, 59-78.
  7. K. Murota (1997): Characterizing a valuated delta-matroid as a family of delta-matroids, J. Operations Research Society of Japan, 40, 565-578.
  8. K. Murota (1998): Fenchel-type duality for matroid valuations, Mathematical Programming, 82, 357-375.
    - Original full version: Bonn report, OR95841, 1995.
  9. K. Murota (1998): On the degree of mixed polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 20, 196-227.
  10. K. Murota and A. Tamura (2001): On circuit valuation of matroids, Advances in Applied Mathematics, 26, 192-225.
  11. T. Maehara and K. Murota (2015): Valuated matroid-based algorithm for submodular welfare problem, Annals of Operations Research, 229, 565-590.
  12. K. Murota (2018): Multiple exchange property for M#-concave functions and valuated matroids, Mathematics of Operations Research, 43, 781-788.
  13. K. Murota (2018): A stronger multiple exchange property for M#-concave functions, Japan Journal of Industrial and Applied Mathematics, 35, 411-421.
  14. K. Murota and K. Takazawa (2020): Relationship of two formulations for shortest bibranchings, Japan Journal of Industrial and Applied Mathematics, On-line: https://doi.org/10.1007/s13160-020-00432-0
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
  1. 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.
  2. 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
  1. K. Murota (1983): LU-decomposition of a matrix with entries of different kinds, Linear Algebra and Its Applications, 49, 275-283.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. K. Murota (1987): Refined study on structural controllability of descriptor systems by means of matroids, SIAM Journal on Control and Optimization, 25, 967-989.
  7. K. Murota (1989): On the irreducibility of layered mixed matrices, Linear and Multilinear Algebra, 24 (1989), 273-288.
  8. K. Murota (1989): Some recent results in combinatorial approaches to dynamical systems, Linear Algebra and Its Applications, 122/123/124, 725-759
  9. K. Murota (1989/90): Combinatorial dynamical system theory - General framework and controllability criteria, Discrete Applied Mathematics, 22, 241-265.
  10. K. Murota (1989): A matroid-theoretic approach to structurally fixed modes of control systems, SIAM Journal on Control and Optimization, 27, 1381-1402.
  11. K. Murota (1990): Eigensets and power products of a bimatroid, Advances in Mathematics, 80, 78-91.
  12. K. Murota (1990): Principal structure of layered mixed matrix, Discrete Applied Mathematics, 27, 221-234.
  13. K. Murota and S. Poljak (1990): Note on a graph-theoretic criterion for structural output controllability, IEEE Transactions on Automatic Control, 35, 939-942.
  14. 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.
  15. K. Murota (1991): On the Smith normal form of structured polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 12, 747-765.
  16. K. Murota (1993): Hierarchical decomposition of symmetric discrete systems by matroid and group theories, Mathematical Programming, Series A, 59, 377-404.
  17. K. Murota (1993): On the Smith normal form of structured polynomial matrices II, SIAM Journal on Matrix Analysis and Applications, 14, 1103-1111.
  18. 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.
  19. S. Iwata and K. Murota (1995): A theorem on the principal structure for independent matchings, Discrete Applied Mathematics, 61, 229-244.
  20. 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.
  21. 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.
  22. K. Murota and M. Scharbrodt (1998): Computing the combinatorial canonical form of a layered mixed matrix, Optimization and Mathematical Software, 10, 373-391.
  23. K. Murota (1998): On the degree of mixed polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 20, 196-227.
  24. J. Geelen, S. Iwata, and K. Murota (2003): The linear delta-matroid parity problem, J. Combinatorial Theory, B88, 377-398.
  25. K. Murota (2012): Legendre duality in combinatorial study of matrix pencils, Japan Journal of Industrial and Applied Mathematics, 29, 205-236.
- Expositions in Japanese
  1. ��c��Y (1991): ��U�V�X�e��̕s�ςȊK�w�\��߂� --- �O��t��}�g��C�h��, ��p��C1, 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).
  2. ��c��Y (1992): �}�g��C�h�ƃV�X�e��. �u��U�\��ƃA��S��Y��I�v (��d�� )�C�ߑ�Ȋw��, ��2��, 57-109.
  3. ��c��Y (2002): ��H�w�ւ̗U��F ��s��̘b (��w�H�w��v��H�w�Ȑ��H�w�R�[�X��), ��{�]�_��, ��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
  1. K. Murota (1990): Computing Puiseux-series solutions to determinantal equations via combinatorial relaxation, SIAM Journal on Computing, 19, 1132-1161.
  2. K. Murota (1995): Computing the degree of determinants via combinatorial relaxation, SIAM Journal on Computing, 24, 765-796.
  3. 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.
  4. K. Murota (1995): An identity for matching and skew-symmetric determinant, Linear Algebra and Its Applications, 218, 1-27.
  5. K. Murota (1995): An identity for bipartite matching and symmetric determinant, Linear Algebra and Its Applications, 222, 261-274.
  6. 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.
  7. 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.
  K. Ikeda and K. Murota (2010): Imperfect Bifurcation in Structures and Materials: Engineering Use of Group-Theoretic Bifurcation Theory, 2nd ed., Springer.
  K. Ikeda and K. Murota (2019): Imperfect Bifurcation in Structures and Materials: Engineering Use of Group-Theoretic Bifurcation Theory, 3rd ed., Springer.
- 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
  1. 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.
  2. K. Murota and K. Ikeda (1991): Critical imperfection of symmetric structures. SIAM Journal on Applied Mathematics, 51, 1222-1254.
  3. K. Ikeda and K. Murota (1991): Bifurcation analysis of symmetric structures using block-diagonalization, Computer Methods in Applied Mechanics and Engineering, 86, 215-243.
  4. K. Murota and K. Ikeda (1992): On random imperfections for structures of regular-polygonal symmetry, SIAM Journal on Applied Mathematics, 52, 1780-1803.
  5. K. Ikeda and K. Murota (1993): Statistics of normally distributed random initial imperfections. International Journal of Solids and Structures, 30, 2445-2467.
  6. K. Murota (1993): Hierarchical decomposition of symmetric discrete systems by matroid and group theories, Mathematical Programming, Series A, 59, 377-404.
  7. K. Ikeda, K. Murota and M. Nakano (1994): Echelon modes in uniform materials. International Journal of Solids and Structures, 31, 2709-2733.
  8. K. Ikeda and K. Murota (1997): Recursive bifurcation as sources of complexity in soil shearing behavior, Soils and Foundations, 37, 17-29.
  9. 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.
  10. 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.
  11. K. Murota, K. Ikeda and K. Terada (1999): Bifurcation mechanism underlying echelon-mode formation, Computer Methods in Applied Mechanics and Engineering, 170, 423-448.
  12. R. Tanaka and K. Murota (1999): Fault-tolerance of control systems with dihedral group symmetry, Trans. Soc. Instr. Control Engin., 35, 806-813.
  13. R. Tanaka and K. Murota (2000): Quantitative analysis for controllability of symmetric control systems, International Journal of Control, 73, 254-264.
  14. R. Tanaka and K. Murota (2000): Symmetric failures in symmetric control systems, Linear Algebra and Its Applications, 318, 145-172.
  15. 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.
  16. 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.
  17. 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.
  18. 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).
  19. 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.
  20. 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.
  21. 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.
  22. T. Maehara and K. Murota (2011): Simultaneous singular value decomposition, Linear Algebra and Its Applications, 435, 106-116.
  23. 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.
  24. 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
  1. 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.
  2. 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
  3. 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
  4. K. Ikeda, K. Murota, and Y. Takayama (2017): Stable economic agglomeration patterns in two dimensions: beyond the scope of central place theory, Journal of Regional Science, 57, 132-172.
  5. K. Ikeda, K. Murota, T. Akamatsu, and Y. Takayama (2017): Agglomeration patterns in a long narrow economy of a new economic geography model: analogy to a racetrack economy, International Journal of Economic Theory, 13, 113-145.
Semidefinite Programming
- Papers
  1. 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
  2. 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
  3. 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.
  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.
Numerical Analysis
- Books in Japanese
  
  M. Sugihara and K. Murota (1994): Elements of Numerical Computations, Iwanami (in Japanese)
  [��C��c��Y (1994): ��l�v�Z�@�̐��. ��g��X]
  M. Sugihara and K. Murota (2009): Theoretical Numerical Linear Algebra, Iwanami (in Japanese)
  [��, ��c��Y (2009): ��`�v�Z�̐��. ��g��X]
- Papers
  1. ��c��Y (1980)�F ��̕ό`Newton�@�̑��I��, ��񏈗��w��_��C21, 469-474.
  2. K. Murota (1982): Global convergence of a modified Newton iteration for algebraic equations. SIAM Journal on Numerical Analysis, 19, 793-799.
  3. K. Murota and M. Iri (1982): Parameter tuning and repeated application of the IMT-type transformation in numerical quadrature, Numerische Mathematik, 38, 347-363.
  4. M. Sugihara and K. Murota (1982): A note on Haselgrove's method for numerical integration, Mathematics of Computation, 39, 549-554.
  5. ��c��Y (1993)�F ��p�d�ז@�ɂ��X�L�[��́u�s�ϐ��v�ɂ��āD ��񏈗��w��_��C34, 533-535.
  6. K. Murota (1993): On "invariance" of schemes in the fundamental solutions method, Trans. Information Processing Society of Japan, 34, 533-535.
  7. K. Tanaka, M. Sugihara, and K. Murota (2004): Numerical indefinite integration by double exponential sinc method, Mathematics of Computation, 74, 655-679.
  8. �� C�� F�ׁC��c ��Y�C�� (2007)�F ��ْl�v�Z�̂��߂� dqds �@�� mdLVs �@�̎��ɂ��āD ��{��p��w��_��C��17��C97-131.
  9. 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.
  10. 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.
  11. 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.
  12. K. Tanaka, M. Sugihara, and K. Murota (2009): Function classes for successful DE-Sinc approximations, Mathematics of Computation, Vol.78 (2009), pp.1553-1571.
  13. K. Tanaka, M. Sugihara, K. Murota, and M. Mori (2009): Function classes for double exponential integration formulas, Numerische Mathematik, 111, 631-655.
  14. 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
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. S. Ito and K. Murota (2016): An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach, SIAM Journal on Matrix Analysis and Applications, 37, 409-419.
  20. K. Murota and T. Matsuo (2023): Double-Exponential transformation: A quick review of a Japanese tradition, to appear in Tokyo Intelligencer, ICIAM 2003, Tokyo. arXiv: http://arxiv.org/abs/2301.01920
Others