• PhD Prague 1983

Peter Butkovic arrived in Birmingham in 1991 as a lecturer in Combinatorial Optimisation. He joined the research group led by Professor R.A.Cuninghame-Green with whom he enjoyed many years of fruitful collaboration.

Peter was the Principal Investigator of several EPSRC funded research projects. The most recent (2008-11) concentrated on the area of reachability of tropical eigenspaces by matrix orbits which finds its application in solving the problems of stability of multiprocessor interactive systems.

Peter gave lectures at more than 60 international conferences and seminars. In 2003 he organised an International Workshop on Max-Algebra in Birmingham and more recently two minisymposia on max-algebra for the International Linear Algebra Society.

During his appointment in Birmingham he introduced new courses in the School of Mathematics such as Game Theory, Research Frontiers in Management Mathematics and History of Optimisation. He taught Combinatorial Optimisation almost every year between 1991 and 2011. Peter has also designed a number of new undergraduate programmes. He completed 6 postgraduate supervisions and supervised a post-doctoral researcher.

• Single Honours Mathematics (G100, G103, G141) 
•  Mathematics Majors: Mathematics with Business Management (G1N2) 
•  Joint Honours Mathematics: Mathematics & Computer Science (GG14) 
•  Pure Mathematics & Computer Science (GGC4) 
•  Mathematics & Sport Science (GC17) 
•  Mathematics & Music (GW13) 
•  Mathematics & Philosophy (GV15) 
•  Mathematics Minors: French Studies and Mathematics (GR11); German Studies and Mathematics (GR12) 
•  Natural Sciences (CFG0, FCG0)

• Tropical linear algebra 
• Applications of tropical linear algebra

RESEARCH THEMES

• Tropical linear algebra (current)
• Combinatorial optimisation (past)
• Applied discrete mathematics (past)
• Computational complexity (past)

RESEARCH ACTIVITY 

• Peter’s research monograph on max-algebra commissioned by Springer was published in September 2010. This book provides an introductory text to max-algebra and presents results on advanced topics. The theory in the first five chapters is self-contained and may be used as support for undergraduate or postgraduate courses. Chapters 6-10 cover more advanced topics with emphasis on feasibility and reachability. The book has been written for a wide-ranging readership, from undergraduate and postgraduate students to researchers and mathematicians working in industry, commerce or management.
• Publication of the first ever paper on max-linear programming in 2010 which created the foundations of a new branch of optimisation and tropical mathematics. It widens the range of applications of max-algebra.
• Polynomial method for narrowing the search for generalised eigenvalues, which is one of the most intractable problems in tropical linear algebra. This method reduces the set of candidates for eigenvalues; in some cases it identifies the whole spectrum.
• (With R. A. Cuninghame-Green) Pseudopolynomial alternating method for solving two-sided max-linear systems. It provides one of the most efficient available tools for solving these systems to date.
• Peter was involved in the application of the max-algebraic spectral theory to the diagonal scaling of matrices. It has been proved that max-algebra can be used to efficiently describe all solutions to a class of combinatorial problems. It is one of the results of the EPSRC funded research, achieved in collaboration with Prof. H. Schneider (University of Wisconsin, Madison).
• Criteria for robustness of matrices in max-algebra. These results provide an efficient characterisation of matrices whose orbit will reach an eigenspace with any starting vector. Equivalently, they characterise production matrices for which the production process based on interactively working processors will reach a steady regime independently of starting times.
• Fast method for finding all essential coefficients of a characteristic maxpolynomial. This problem, which finds applications in managerial decision making (it is essentially the so called “job rotation problem”), is of undecided computational complexity. However it was shown that many special cases are efficiently solvable. It is one of the results of Peter’s EPSRC funded research, achieved in collaboration with Prof. R. E. Burkard (Graz University of Technology, Austria).
• (With S. Gaubert and R. A. Cuninghame-Green) Complete solution of the minimal-dimensional realisation (MDR) problem for convex sequences. This result presents a new connection between classical inequalities theory and modern theory of discrete-dynamic systems. MDR for general sequences is a hard, unresolved problem.
• Finding and proving that the solution set of any two-sided max-linear system is finitely generated (1982). This is a theoretical result of fundamental importance cited by many authors. It was discovered well before other researchers attempted to solve the problem.
• Finding the equivalence between the strong regularity of matrices and uniqueness of the optimal solution to the assignment problem (1983). This result revealed a link between two seemingly unrelated questions long before it was studied in other research centres worldwide and gave rise to a number of findings.

In 2009 P Butkovic acted as a consultant for KTN Industrial Mathematics Internship of his research student working at BT Research.

Selected publications:

Butkovič, P., Schneider, H. and Sergeev, S., Recognising weakly stable matrices, to appear in SIAM J. Control and Optimization.

Butkovič, P., Schneider, H. and Sergeev, S. (2012), Z-matrix equations in max algebra, nonnegative linear algebra and other semirings, Linear and Multilinear Algebra: 1-20.

Butkovič, P. (2010), Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag.

Sergeev, S., Schneider, H. and Butkovič, P. (2009), On visualisation scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra and its Applications 431: 2395–2406

Butkovič, P., Cuninghame-Green, R.A.and Gaubert, S. (2009), Reducible spectral theory with applications to the robustness of matrices in max-algebra, SIAM Journal on Matrix Analysis and Applications 31(3): 1412-1431

Butkovič, P. and Aminu, A. (2009), Max-linear programming. IMA Journal of Management Mathematics 20(3): 1-17

Butkovič, P. (2008), Finding a bounded mixed-integer solution to a system of dual inequalities, Operations Research Letters 36: 623-627

Butkovič, P. (2008), Permuted max-algebraic (tropical) eigenvector problem is NP-complete. Linear Algebra and its Applications 428: 1874-1882

Butkovič, P. and Cuninghame-Green, R.A. (2007), The eigenproblem for matrix powers in max-algebra, Linear Algebra and Its Applications 421: 370-381

Butkovič, P., Schneider, H. and Sergeev, S. (2007), Generators, extremals and bases of max cones, Linear Algebra and Its Applications 421: 394-406

Butkovič, P. and Schneider, H. (2005), Applications of max-algebra to diagonal scaling of matrices, Electronic Journal of Linear Algebra 13: 262-273

Burkard, R.E. and Butkovič, P. (2003), Max algebra and the linear assignment problem, Mathematical Programming, Ser.B 98: 415-429

Cuninghame-Green, R.A. and Butkovič, P. (2003), The equation Ax = By over (max, +), Theoretical Computer Science 293: 3-12

Butkovič, P. (2003), Max-algebra: the linear algebra of combinatorics? Linear Algebra and Its Applications 367: 313-335

Burkard, R.E. and Butkovič, P. (2003), Finding all essential terms of a characteristic maxpolynomial, Discrete Applied Mathematics 130: 367-380

Butkovič, P. (2000), The simple image set of (max, +) linear mappings, Discrete Applied Mathematics 105: 73-86