Publications of K. Murota

Discrete Convex Analysis

Books

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 1922, 2012.

Minimization and maximization algorithms
in discrete convex analysis [
slide
,
video
] at Modern Aspects of Submodularity, Georgia Institute of Technology,
March 1922, 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)

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

Abstract

Part 1 (Convex Analysis View on Combinatorial Optimization)
[
video
]

Part 2 (Properties of Lconvex and Mconvex 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 HungarianJapanese 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.

Mconvex 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. 253278

K. Murota (2000):
Algorithms in discrete convex analysis,
IEICE Transactions on Systems and Information,
E83D, 344352.

K. Murota (2001):
Lconvex functions and Mconvex functions,
Encyclopedia of Optimization,
P. M. Pardalos and C. A. Floudas, eds., Kluwer, 111118

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,
SpringerVerlag, Berlin, 2009, Chapter 11, 219260.

K. Murota (2015):
Discrete convex analysis,
Supplemantary material for
Summer School (September 2125, 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, 151273.
(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.23, 472518.

K. Murota (2021):
On basic operations related to network induction of discrete convex functions,
Vol.36 (2021), Nos.23, 519559.

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,
to appear.
arXiv: https://arxiv.org/abs/2111.07240

K. Murota and A. Tamura (2023):
Recent progress on integrally convex functions.
Japan Journal of Industrial and Applied Mathematics,
https://doi.org/10.1007/s13160023005894
(Open access)

Papers

K. Murota (1996): Valuated matroid intersection, I: optimality criteria,
SIAM Journal on Discrete Mathematics,
9, 545561.

K. Murota (1996): Valuated matroid intersection, II: algorithms.
SIAM Journal on Discrete Mathematics,
9, 562576.

K. Murota (1996):
Convexity and Steinitz's exchange property,
Advances in Mathematics, 124, 272311.

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 35, 1996.
Lecture Notes in Computer Science 1084, SpringerVerlag, 1996,
pp.260274.

K. Murota (1998):
Discrete convex analysis, Mathematical Programming, 83, 313371.

K. Murota (1999):
Submodular flow problem with a nonseparable cost function,
Combinatorica, 19, 87109.

K. Murota and A. Shioura (1999):
MConvex function on generalized polymatroid,
Mathematics of Operations Research,
24, 95105.
[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. 253278

S. Fujishige and K. Murota (2000):
Notes on L/Mconvex functions and the separation theorems,
Mathematical Programming,
88, 129146.

K. Murota and A. Shioura (2000):
Extension of Mconvexity and Lconvexity
to polyhedral convex functions,
Advances in Applied Mathematics,
25 (2000), 352427.

K. Murota (2000):
Algorithms in discrete convex analysis,
IEICE Transactions on Systems and Information,
E83D, 344352.

K. Murota and A. Shioura (2001):
Relationship of M/Lconvex functions with
discrete convex functions by Miller and by FavatiTardella,
Discrete Applied Mathematics,
115, 151176.

V. Danilov, G. Koshevoy, and K. Murota (2001):
Discrete convexity and equilibria in economies with indivisible
goods and money,
Mathematical Social Sciences, 41, 251273

S. Moriguchi, K. Murota and A. Shioura (2002):
Scaling algorithms for Mconvex function minimization,
IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences,
E85A, 922929.

K. Murota and A. Shioura (2003):
Quasi Mconvex and Lconvex functionsQuasiconvexity
in discrete optimization,
Discrete Applied Mathematics,
131/132, 467494.

S. Moriguchi and K. Murota (2003):
Capacity scaling algorithm for scalable Mconvex submodular flow problems,
Optimization Methods and Software, 18, 207218.

K. Murota (2003):
On steepest descent algorithms for discrete convex functions,
SIAM Journal on Optimization, 14, 699707.

K. Murota and A. Tamura (2003):
Application of Mconvex submodular flow problem to mathematical economics,
Japan Journal of Industrial and Applied Mathematics,
20, 257277.

Twelfth Annual International Symposium
on Algorithms and Computation (ISAAC 01),
Christchurch, New Zealand,
December 1921, 2001

K. Murota and A. Tamura (2003):
New characterizations of Mconvex functions and
their applications to economic equilibrium models with
indivisibilities, Discrete Applied Mathematics, 131, 495512.
Also in the special volume Discrete Applied Mathematics,
Editors' Choice, Edition 2003.

K. Murota and A. Shioura (2004):
Conjugacy relationship between Mconvex and Lconvex functions
in continuous variables,
Mathematical Programming, 101, 415433.

K. Murota and A. Tamura (2004):
Proximity theorems of discrete convex functions,
Mathematical Programming, A99, 539562.

K. Murota and A. Shioura (2004):
Fundamental properties of Mconvex and Lconvex
functions in continuous variables,
IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences,
E87A, 10421052.

H. Hirai and K. Murota (2004):
Mconvex functions and tree metrics,
Japan Journal of Industrial and Applied Mathematics, 21, 391403.

K. Murota, H. Saito, and R. Weismantel (2004):
Optimality criteria for a class of nonlinear integer programs,
Operations Research Letters,
32, 468472.

K. Murota and A. Shioura (2005):
Substitutes and complements in network flows
viewed as discrete convexity,
Discrete Optimization, 2, 256268.

S. Moriguchi and K. Murota (2005):
Discrete Hessian matrix for Lconvex functions,
IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences,
E88A, 11041108.

S. Iwata, S. Moriguchi and K. Murota (2005):
A capacity scaling algorithm for Mconvex submodular flow,
Mathematical Programming, 103, 181202.

K. Murota (2005):
Note on multimodularity and Lconvexity,
Mathematics of Operations Research,
30, 658661.

T. Iimura, K. Murota and A. Tamura (2005):
Discrete fixed point theorem reconsidered,
Journal of Mathematical Economics,
41, 10301036.

K. Murota (2006):
Mconvex functions on jump systems:
A general framework for minsquare graph factor problem,
SIAM Journal on Discrete Mathematics,
20, 213226.

K. Murota and K. Tanaka (2006):
A steepest descent algorithm for Mconvex functions on jump systems,
IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences,
E89A, 11601165.

Y. Kobayashi, K. Murota and K. Tanaka (2007):
Operations on Mconvex functions on jump systems,
SIAM Journal on Discrete Mathematics,
21, 107129.

Y. Kobayashi and K. Murota (2007):
Induction of Mconvex functions by linking systems,
Discrete Applied Mathematics,
155, 14711480.

K. Murota and A. Shioura (2008):
Note on the continuity of Mconvex and Lconvex functions
in continuous variables,
Journal of the Operations Research Society of Japan,
51, 265273.

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,
SpringerVerlag, Berlin, 2009, Chapter 11, 219260.

K. Murota (2010):
Submodular function minimization and maximization in discrete convex analysis,
RIMS Kokyuroku Bessatsu, B23, 193211.

Y. Kobayashi, K. Murota and R. Weismantel (2012):
Cone superadditivity of discrete convex functions,
Mathematical Programming, Series A, 135, 2544.

S. Moriguchi and K. Murota (2012):
On discrete Hessian matrix and convex extensibility,
Journal of the Operations Research Society of Japan, 55, 4862.

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, 588592.

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, 468478, 2013.

K. Murota and A. Shioura (2014):
Dijkstra's algorithm and Lconcave function maximization,
Mathematical Programming, Series A, 145, 163177.

K. Murota and A. Shioura (2014):
Exact bounds for steepest descent algorithms of Lconvex function minimization,
Operations Research Letters, 42, 361366.

K. Murota and Y. Yokoi (2015):
On the lattice structure of stable allocations in twosided discreteconcave market,
Mathematics of Operations Research, 40, 460473.

T. Maehara and K. Murota (2015):
A framework of discrete DC programming by discrete convex analysis,
Mathematical Programming, Series A, 152, 435466.

S. Fujishige, K. Murota and A. Shioura (2015):
Monotonicity in steepest ascent algorithms for polyhedral Lconcave functions,
Journal of the Operations Research Society of Japan, 58, 184208.

K. Murota (2015):
On polyhedral approximation of Lconvex and Mconvex functions,
Journal of the Operations Research Society of Japan, 58, 291305.

K. Murota, A. Shioura, and Z. Yang (2016):
Time bounds for iterative auctions:
A unified approach by discrete convex analysis,
Discrete Optimization, 19, 3662.
[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, 151273.
(Revised version available at
http://arxiv.org/abs/2212.03598)

K. Murota and A. Shioura (2017):
Note on time bounds of twophase algorithms
for Lconvex function minimization,
Japan Journal of Industrial and Applied Mathematics,
Vol. 34 (2017), pp.429440.

T. Maehara, N. Marumo, and K. Murota (2018):
Continuous relaxation for discrete DC programming,
Mathematical Programming, Series B,
Vol.169 (2018), pp.199219.
DOI 10.1007/s1010701711392

K. Murota (2018):
Multiple exchange property for M#concave functions and valuated matroids,
Mathematics of Operations Research,
Vol. 43 (2018) pp. 781788.

Y. Iwamasa, K. Murota, and S. Zivny (2018):
Discrete convexity in joint winner property,
Discrete Optimization,
Vol.28 (2018), pp.7888.

K. Murota and A. Shioura (2018):
Simpler exchange axioms for Mconcave functions
on generalized polymatroids,
Japan Journal of Industrial and Applied Mathematics,
Vol.35 (2018), No.1, pp.235259.

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

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

H. Hirai, Y. Iwamasa, K. Murota, and S. Zivny (2018):
Beyond JWP: A tractable class of binary VCSPs via Mconvex 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 Mconvex 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 "OrderBased Cost Optimization in AssembletoOrder Systems" by Lu and Song (2005),
Operations Research, Vol. 67, No.1 (2019), pp.163166.
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), 283298.

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, 5363.
[Errata]

S. Moriguchi, K. Murota, A. Tamura, and F. Tardella (2019):
Scaling, proximity, and optimization of integrally convex functions,
Mathematical Programming, Vol.175 (2019), 119154.

S. Moriguchi, K. Murota, A. Tamura, and F. Tardella (2020):
Discrete midpoint convexity,
Mathematics of Operations Research,
Vol. 45 (2020), 99128.
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), 195208.
https://link.springer.com/article/10.1007/s11590019015011

K. Murota (2021):
A survey of fundamental operations on discrete convex functions of various kinds,
Optimization Methods and Software,
Vol.36 (2021), Nos.23, 472518.

K. Murota (2021):
On basic operations related to network induction of discrete convex functions,
Vol.36 (2021), Nos.23, 519559.

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.141161.
https://doi.org/10.1007/s13160020004320

K. Murota (2021):
A note on Mconvex functions on jump systems,
Discrete Applied Mathematics,
Vol.289 (2021), 492502.

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 minmax formula for boxTDI polyhedra,
Mathematics of Operations Research,
Vol.47 (2022), No.2, 10261047.
Published online (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 Mconvex sets: Background and structures,
Mathematical Programming,
Vol.195 (2022), No.12, 9771025.
https://doi.org/10.1007/s10107021017222
SharedIt link: https://rdcu.be/cAj1K
arXiv: http://arxiv.org/abs/2007.09616

A. Frank and K. Murota (2022):
Decreasing minimization on Mconvex sets: Algorithms and applications,
Mathematical Programming,
Vol.195 (2022), No.12, 10271068.
https://doi.org/10.1007/s10107021017115
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, 599630.
https://doi.org/10.1007/s1316002200499x
(Open access)

A. Frank and K. Murota (2022):
Fair integral submodular flows,
Discrete Applied Mathematics,
Vol.320 (2022), 416434.
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, 13931422.
https://doi.org/10.1287/moor.2022.1303

A. Frank and K. Murota (2023):
Decreasing minimization on basepolyhedra:
Relation between discrete and continuous cases,
Japan Journal of Industrial and Applied Mathematics,
Vol.40 (2023), No.1, 183221.
https://link.springer.com/article/10.1007/s13160022005114 ,
SharedIt link: https://rdcu.be/cPlmC

S. Moriguchi and K. Murota (2023):
Note on the polyhedral description of the Minkowski sum of two Lconvex sets.
Japan Journal of Industrial and Applied Mathematics,
Vol.40 (2023), No.1, 223263.
https://doi.org/10.1007/s13160022005123
(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,
to appear.
arXiv: https://arxiv.org/abs/2111.07240

K. Murota and A. Tamura (2023):
Recent progress on integrally convex functions.
Japan Journal of Industrial and Applied Mathematics,
https://doi.org/10.1007/s13160023005894
(Open access)

K. Murota and A. Tamura (2023):
ShapleyFolkmantype theorem for integrally convex sets.
arXiv: http://arxiv.org/abs/2305.15125

K. Murota and A. Shioura (2023):
Note on minimization of quasi Mnaturalconvex functions.
arXiv: http://arxiv.org/abs/2305.17849

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

Technical Notes

A proof of the Mconvex intersection theorem (January 2004)

On infimal convolution of Mconvex functions (March 2004)

A proof of the Loptimality criterion theorem (July 2004)

Proof of biconjugacy of univariate discrete convex functions (November 2021)

Books and Expositions in Japanese

室田一雄 (1998):
離散凸解析. 「離散構造とアルゴリズムV」
(藤重悟 編)，近代科学社, 第2章, 51100.

室田一雄 (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

Papers

K. Murota (1995):
Finding optimal minors of valuated bimatroids,
Appl. Math. Letters, 8, 3742.

K. Murota (1996):
Two algorithms for valuated deltamatroids
Appl. Math. Letters, 9, 6771.

K. Murota (1996): Valuated matroid intersection, I: optimality criteria,
SIAM Journal on Discrete Mathematics,
9, 545561.

K. Murota (1996): Valuated matroid intersection, II: algorithms.
SIAM Journal on Discrete Mathematics,
9, 562576.

K. Murota (1996):
On exchange axioms for valuated matroids and valuated deltamatroids,
Combinatorica, 6, 591596.

K. Murota (1997):
Matroid valuation on independent sets,
J. Combinatorial Theory, B69, 5978.

K. Murota (1997):
Characterizing a valuated deltamatroid as a family of deltamatroids,
J. Operations Research Society of Japan, 40, 565578.

K. Murota (1998): Fencheltype duality for matroid valuations,
Mathematical Programming, 82, 357375.

K. Murota (1998):
On the degree of mixed polynomial matrices,
SIAM Journal on Matrix Analysis and Applications,
20, 196227.

K. Murota and A. Tamura (2001):
On circuit valuation of matroids,
Advances in Applied Mathematics,
26, 192225.

T. Maehara and K. Murota (2015):
Valuated matroidbased algorithm for submodular welfare problem,
Annals of Operations Research, 229, 565590.

K. Murota (2018):
Multiple exchange property for M#concave functions and valuated matroids,
Mathematics of Operations Research,
43, 781788.

K. Murota (2018):
A stronger multiple exchange property for M#concave functions,
Japan Journal of Industrial and Applied Mathematics,
35, 411421.

K. Murota and K. Takazawa (2020):
Relationship of two formulations for shortest bibranchings,
Japan Journal of Industrial and Applied Mathematics,
Online:
https://doi.org/10.1007/s13160020004320

Combinatorial Matrix Theory

Surveys

K. Murota (1993): Mixed matrices  Irreducibility and decomposition.
Combinatorial and GraphTheoretic 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 37, 1995) Klaus Kirchgaessner, Osker Mahrenholtz, and Reinhard
Mennicken, eds., Mathematical Research, Vol. 87,
Akademie Verlag, pp. 257279.

Papers

K. Murota (1983):
LUdecomposition of a matrix with entries of different kinds,
Linear Algebra and Its Applications, 49, 275283.

K. Murota and M. Iri (1985):
Structural solvability of systems of equationsA mathematical
formulation for distinguishing accurate and inaccurate numbers
in structural analysis of systems,
Japan Journal of Applied Mathematics, 2, 247271.

K. Murota (1985):
Use of the concept of physical dimensions in the structural approach
to systems analysis,
Japan Journal of Applied Mathematics, 2, 471494.

K. Murota (1987):
Mengerdecomposition of a graph and its application to the
structural analysis of a largescale system of equations,
Discrete Applied Mathematics, 17, 107134.

K. Murota, M. Iri and M. Nakamura (1987):
Combinatorial canonical form of layered mixed matrices and its
application to blocktriangularization of systems of equations,
SIAM Journal on Algebraic and Discrete Methods, 8, 123149.

K. Murota (1987):
Refined study on structural controllability of descriptor
systems by means of matroids,
SIAM Journal on Control and Optimization, 25, 967989.

K. Murota (1989):
On the irreducibility of layered mixed matrices,
Linear and Multilinear Algebra, 24 (1989), 273288.

K. Murota (1989):
Some recent results in combinatorial approaches to dynamical systems,
Linear Algebra and Its Applications, 122/123/124, 725759

K. Murota (1989/90):
Combinatorial dynamical system theory  General framework and
controllability criteria,
Discrete Applied Mathematics, 22, 241265.

K. Murota (1989):
A matroidtheoretic approach to structurally fixed modes
of control systems,
SIAM Journal on Control and Optimization, 27, 13811402.

K. Murota (1990):
Eigensets and power products of a bimatroid,
Advances in Mathematics, 80, 7891.

K. Murota (1990):
Principal structure of layered mixed matrix,
Discrete Applied Mathematics, 27, 221234.

K. Murota and S. Poljak (1990):
Note on a graphtheoretic criterion for structural output controllability,
IEEE Transactions on Automatic Control, 35, 939942.

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, 878894.

K. Murota (1991):
On the Smith normal form of structured polynomial matrices,
SIAM Journal on Matrix Analysis and Applications,
12, 747765.

K. Murota (1993):
Hierarchical decomposition of symmetric discrete systems by matroid
and group theories,
Mathematical Programming, Series A, 59, 377404.

K. Murota (1993):
On the Smith normal form of structured polynomial matrices II,
SIAM Journal on Matrix Analysis and Applications,
14, 11031111.

H. Ito, S. Iwata and K. Murota (1994):
Blocktriangularization of partitioned matrices
under similarity/equivalence transformations,
SIAM Journal on Matrix Analysis and Applications,
15, 12261255.

S. Iwata and K. Murota (1995):
A theorem on the principal structure for independent matchings,
Discrete Applied Mathematics, 61, 229244.

S. Iwata and K. Murota (1995):
A minimax theorem and a DulmageMendelsohn type decomposition
for a class of generic partitioned matrices,
SIAM J. Matrix Analy. Appl., 16, 719734.

S. Iwata and K. Murota (1996):
Horizontal principal structure of layered mixed matrices
 Decomposition of discrete systems by designvariable selections,
SIAM J. Disc. Math., 9, 7186.

K. Murota and M. Scharbrodt (1998):
Computing the combinatorial canonical form
of a layered mixed matrix,
Optimization and Mathematical Software, 10, 373391.

K. Murota (1998):
On the degree of mixed polynomial matrices,
SIAM Journal on Matrix Analysis and Applications,
20, 196227.

J. Geelen, S. Iwata, and K. Murota (2003):
The linear deltamatroid parity problem,
J. Combinatorial Theory, B88, 377398.

K. Murota (2012):
Legendre duality in combinatorial study of matrix pencils,
Japan Journal of Industrial and Applied Mathematics,
29, 205236.

Expositions in Japanese

室田一雄 (1991):
離散システムの不変な階層構造を求めて  グラフからマトロイドへ,
応用数理，1, 230248.
(Hierarchical decompositions of discrete systems  exploiting invariant
structure by matroid; Bulletin of the Japan Society for Industrial and
Applied Mathematics, 1, 230248).

室田一雄 (1992):
マトロイドとシステム解析. 「離散構造とアルゴリズムI」
(藤重悟 編)，近代科学社, 第2章, 57109.

室田一雄 (2002):
数理工学への誘い： 混合行列の話
(東京大学工学部計数工学科数理情報工学コース編),
日本評論社, 第13章, 139149.
Combinatorial Relaxation

Books

Papers

K. Murota (1990):
Computing Puiseuxseries solutions to determinantal equations via
combinatorial relaxation,
SIAM Journal on Computing, 19, 11321161.

K. Murota (1995):
Computing the degree of determinants via combinatorial relaxation,
SIAM Journal on Computing, 24, 765796.

K. Murota (1995): Combinatorial relaxation algorithm for the
maximum degree of subdeterminants: Computing SmithMcMillan form at
infinity and structural indices in Kronecker form.
Applicable Algebra in Engineering, Communication and Computing,
6, 251273.

K. Murota (1995):
An identity for matching and skewsymmetric determinant,
Linear Algebra and Its Applications,
218, 127.

K. Murota (1995):
An identity for bipartite matching and symmetric determinant,
Linear Algebra and Its Applications, 222, 261274.

S. Iwata, K. Murota and I. Sakuta (1996):
Primaldual combinatorial relaxation algorithms
for the maximum degree of subdeterminants,
SIAM J. Scientific Computing, 17, 9931012.

S. Iwata and K. Murota (2001):
Combinatorial relaxation algorithm for mixed polynomial matrices,
Mathematical Programming, Series A,
90, 353371.
GroupTheoretic Methods in Engineering

Books

Tutorial Slides

Softwares

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, 273297.

K. Murota and K. Ikeda (1991): Critical imperfection of symmetric
structures. SIAM Journal on Applied Mathematics, 51, 12221254.

K. Ikeda and K. Murota (1991):
Bifurcation analysis of symmetric structures using blockdiagonalization,
Computer Methods in Applied Mechanics and Engineering,
86, 215243.

K. Murota and K. Ikeda (1992):
On random imperfections for structures of regularpolygonal symmetry,
SIAM Journal on Applied Mathematics, 52, 17801803.

K. Ikeda and K. Murota (1993): Statistics of normally distributed random
initial imperfections. International Journal of Solids and Structures,
30, 24452467.

K. Murota (1993):
Hierarchical decomposition of symmetric discrete systems by matroid
and group theories,
Mathematical Programming, Series A, 59, 377404.

K. Ikeda, K. Murota and M. Nakano (1994):
Echelon modes in uniform materials.
International Journal of Solids and Structures, 31, 27092733.

K. Ikeda and K. Murota (1997):
Recursive bifurcation as sources of complexity in soil shearing
behavior,
Soils and Foundations, 37, 1729.

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, 19291953.

K. Ikeda and K. Murota (1999):
Systematic description of imperfect bifurcation behavior of
symmetric systems,
International Journal of Solids and Structures,
36, No. 11, 15611596.

K. Murota, K. Ikeda and K. Terada (1999):
Bifurcation mechanism underlying echelonmode formation,
Computer Methods in Applied Mechanics and Engineering,
170, 423448.

R. Tanaka and K. Murota (1999):
Faulttolerance of control systems with dihedral group symmetry,
Trans. Soc. Instr. Control Engin.,
35, 806813.

R. Tanaka and K. Murota (2000):
Quantitative analysis for controllability of symmetric control systems,
International Journal of Control, 73, 254264.

R. Tanaka and K. Murota (2000):
Symmetric failures in symmetric control systems,
Linear Algebra and Its Applications,
318, 145172.

Y. Kanno, M. Ohsaki, K. Murota, and N. Katoh (2001):
Group symmetry in interiorpoint methods for semidefinite program,
Optimization and Engineering,
2, 293320.

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, 497515.

K. Ikeda, K. Murota, A. Yanagimoto and H. Noguchi (2007):
Improvement of the scaled corrector method for
bifurcation analysis using
symmetryexploiting blockdiagonalization,
Computer Methods in Applied Mechanics and Engineering,
196, 16481661.

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 (14).

K. Murota, Y. Kanno, M. Kojima and S. Kojima (2010):
A numerical algorithm for blockdiagonal decomposition
of matrix *algebras
with application to semidefinite programming,
Japan Journal of Industrial and Applied Mathematics,
27, 125160.

T. Maehara and K. Murota (2010):
A numerical algorithm for blockdiagonal decomposition
of matrix *algebras
with general irreducible components,
Japan Journal of Industrial and Applied Mathematics,
27, 263293.

T. Maehara and K. Murota (2010):
Error controlling algorithm for simultaneous blockdiagonalization and
its application to independent component analysis,
JSIAM Letters, 2, 131134.

T. Maehara and K. Murota (2011):
Simultaneous singular value decomposition,
Linear Algebra and Its Applications,
435, 106116.

T. Maehara and K. Murota (2011):
Algorithm for errorcontrolled
simultaneous blockdiagonalization of matrices,
SIAM Journal on Matrix Analysis and Applications,
32, 605620.

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, 12521266.
Economic Geography

Books

Tutorial Slides

Papers

K. Ikeda, K. Murota, T. Akamatsu, T. Kono, Y. Takayama (2011):
Selforganizing hexagons for coreperiphery models:
Central place theory and group theory,
METR 201124,
Department of Mathematical Informatics, University of Tokyo.

K. Ikeda, K. Murota, and T. Akamatsu (2012):
Selforganization of Losch's hexagons
in economic agglomeration for coreperiphery models,
International Journal of Bifurcation and Chaos,
Vol. 22 (2012), No.8, 1230026 (29 pages; 12300261 to 123002629).
Erratum

K. Ikeda, K. Murota, T. Akamatsu, T. Kono, and Y. Takayama (2014):
Selforganization of hexagonal agglomeration patterns in new economic geography models,
Journal of Economic Behavior & Organization, 99, 3252

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, 132172.

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, 113145.
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, 647674

Y. Kanno, M. Ohsaki, K. Murota, and N. Katoh (2001):
Group symmetry in interiorpoint methods for semidefinite program,
Optimization and Engineering, 2, 293320

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, 303327.

K. Murota, Y. Kanno, M. Kojima and S. Kojima (2010):
A numerical algorithm for blockdiagonal decomposition
of matrix *algebras
with application to semidefinite programming,
Japan Journal of Industrial and Applied Mathematics,
27, 125160.
Numerical Analysis

Books in Japanese

Papers

室田一雄 (1980)：
平野の変形Newton法の大域的収束性,
情報処理学会論文誌，21, 469474.

K. Murota (1982): Global convergence of a modified Newton
iteration for algebraic equations. SIAM Journal on Numerical
Analysis, 19, 793799.

K. Murota and M. Iri (1982):
Parameter tuning and repeated application of the IMTtype transformation
in numerical quadrature,
Numerische Mathematik, 38, 347363.

M. Sugihara and K. Murota (1982):
A note on Haselgrove's method for numerical integration,
Mathematics of Computation, 39, 549554.
 室田一雄 (1993)：
代用電荷法におけるスキームの「不変性」について．
情報処理学会論文誌，34, 533535.

K. Murota (1993): On "invariance" of schemes in the fundamental
solutions method, Trans. Information Processing Society of Japan,
34, 533535.

K. Tanaka, M. Sugihara, and K. Murota (2004):
Numerical indefinite integration by double exponential sinc method,
Mathematics of Computation, 74, 655679.

相島 健助，松尾 宇泰，室田 一雄，杉原 正顯 (2007)：
特異値計算のための dqds 法と mdLVs 法の収束性について．
日本応用数理学会論文誌，第17巻，97131.

K. Tanaka, M. Sugihara, and K. Murota (2008):
Complexanalytic approach to the SincGauss sampling formula,
Japan Journal of Industrial and Applied Mathematics,
Vol. 25 (2008), No. 2, 209231.

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, 522537.

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), 6581.

K. Tanaka, M. Sugihara, and K. Murota (2009):
Function classes for successful DESinc approximations,
Mathematics of Computation, Vol.78 (2009), pp.15531571.

K. Tanaka, M. Sugihara, K. Murota, and M. Mori (2009):
Function classes for double exponential integration formulas,
Numerische Mathematik,
111, 631655.

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, 11791187

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 MathforIndustry,
2 (2010A1), 111.

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, 251262.

K. Aishima, T. Matsuo, K. Murota and M. Sugihara (2012):
A Wilkinsonlike multishift QR algorithm for symmetric eigenvalue
problems and its global convergence,
Journal of Computational and Applied Mathematics, 236, 35563560.

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, 132143.

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, 409419.

K. Murota and T. Matsuo (2023):
DoubleExponential transformation:
A quick review of a Japanese tradition,
to appear in
Tokyo Intelligencer, ICIAM 2003, Tokyo.
arXiv: http://arxiv.org/abs/2301.01920
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, 5565.
Included in:
K. Takeuchi:
Contributions on Theory of Mathematical Statistics,
Springer, 2020, Chapter 9, 221235.

Voronoi Diagram

T. Ohya, M. Iri and K. Murota (1984):
A fast Voronoidiagram algorithm with quaternary tree bucketing,
Information Processing Letters, 18, 227231.

M. Iri, K. Murota and T. Ohya (1984):
A fast Voronoidiagram algorithm with applications to geographical
optimization problems,
In System Modelling and Optimization (P. ThoftChristensen, ed.)
Lecture Notes in Control and Information Sciences, 59, Springer,
1984, 273288.

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, 306337.

H. Imai, M. Iri and K. Murota (1985):
Voronoi diagram in the Laguerre geometry and its applications,
SIAM Journal on Computing, 14, 93105.

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., NorthHolland,
1985, 153195.

M. Iri, K. Kubota and K. Murota (1991):
Geometrical/geographical optimization and fast automatic differentiation,
Yugoslav Journal of the Operations Research, 1, 121134.

Graph, Newtork, Matroid, Discrete Optimization

M. Iri, K. Murota and S. Matsui (1981):
Lineartime approximation algorithms for finding the minimumweight
perfect matching on a plane,
Information Processing Letters, 12, 206209.

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

M. Iri, K. Murota and S. Matsui (1983):
Heuristics for planar minimumweight perfect matchings,
Networks, 13, 6792.

K. Murota (1987):
Homotopy base of acyclic graphsA combinatorial
analysis of commutative
diagrams by means of preordered matroid,
Discrete Applied Mathematics, 17, 135155.

K. Murota and S. Fujishige (1987):
Finding a homotopy base for directed paths in an acyclic graph,
Discrete Applied Mathematics, 17, 157162.

K. Murota (1988):
Note on the universal bases of a pair of
polymatroids, Journal of the Operations Research Society of Japan,
31, 565572.

S. Iwata, K. Murota and M. Shigeno (1997):
A fast submodular intersection algorithm for strong map sequences,
Mathematics of Operations Research,
22, 803813.

T. Suzuki. S. Aoki and K. Murota (2005):
Use of primaldual technique in the network algorithm
for twoway contingency tables,
Japan Journal of Industrial and Applied Mathematics,
22, 133145.

H. Hirai, K. Murota, and M. Rikitoku (2005):
SVM kernel by electric network,
Pacific Journal of Optimization,
1, 509526.

H. Saito and K. Murota (2007):
Benders decomposition approach to robust mixed integer programming,
Pacific Journal of Optimization,
3, 99112.

H. Hirai, K. Murota, and M. Rikitoku (2007):
Electric network classifiers for semisupervised learning on graphs,
Journal of the Operations Research Society of Japan,
50, 218231.

K. Otsuki, Y. Kobayashi, and K. Murota (2016):
Improved maxflow mincut algorithms in a circular disk failure model
with application to a road network,
European Journal of Operational Research, 248, 396403.