# Professor Peter Butkovic

## Professor of Applied Discrete Mathematics

## School of Mathematics

### Contact details

School of Mathematics

Watson Building

University of Birmingham

Edgbaston

Birmingham

B15 2TT

UK

## About

Professor Butkovic's main research interest is the theory of max-linear systems, a rapidly evolving area of numerical linear algebra and applied discrete mathematics. He is the author of a research monograph on this subject published in 2010 and he is also the author or co-author of more than 40 peer-reviewed papers.

Peter Butkovic has received a number of grants in support of his research, including those from the EPSRC, LMS and Royal Society. He is the Chair of the LMS joint research group on tropical mathematics and its applications.

Peter has been in charge of a variety of modules such as Combinatorial Optimisation, Game Theory, Research Frontiers in Management Mathematics, Linear Programming, Non-Linear Programming and History of Mathematics. He supervises MSci projects and postgraduate students.

More information can be found on http://web.mat.bham.ac.uk/P.Butkovic/

## Qualifications

- PhD Prague 1983

## Biography

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.

## Teaching

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

## Postgraduate supervision

- Tropical linear algebra
- Applications of tropical linear algebra

## Research

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

## Other activities

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

## Publications

### Selected publications:

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

P.Butkovic, M.MacCaig: A strongly polynomial method for solving integer max-linear programs in a generic case. Journal of Optimization Theory and Applications (2015), Volume 165, Issue 3, pp 941-963.

P.Butkovic, M.MacCaig: On the integer max-linear programming problem, Discrete Applied Mathematics 162 (2014) 128–141,

P.Butkovic, H.Schneider, S.Sergeev and B.-S. Tam: Two cores of a nonnegative matrix, Linear Algebra and its Applications 439 (2013) 1929–1954,

P.Butkovic, M.MacCaig: On integer eigenvectors and subeigenvectors in the max-plus algebra, Linear Algebra and its Applications 438 (2013) 3408–3424.

P.Butkovic, H.Schneider and S.Sergeev: Recognizing weakly stable matrices, SIAM J. Control Optim. 2012, 50(5), 3029-3051.

P.Butkovic and S.Lewis: On the job rotation problem. Discrete Optimization 4 (2007) 163-174.

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.

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